What's wrong with my taxonomy links or my taxonomy view and contextual filter?
You mentioned that changing the alias doesn't update all pre-written aliases. Could you pick one term, edit it, and hit "Automatic alias" under URL aliases so that it updates, then post whether that resolved the issue for that individual term?

If so, all you need is to bulk update aliases for that vocabulary, which can be done with a VBO - I'll detail how if that's the issue.