I understand that concern, though I'm not sure I entirely agree with it, simply for practical reasons. We're not going to be able to include every possible language for every place, anyway, and pretty much every place has a language that most people speak, so it makes sense to use that one more.
As for a programming solution, I haven't done a lot with Mediawiki, so I can't be sure, but I don't know if it's even possible. You can have one category be a redirect to another, but it's discouraged because things put in the redirect category will not appear in the other.
We could put all the cities in New Brunswick into both New Brunswick and Nouveau-Brunswick, though of course that has to be maintained, because probably people will create city categories without thinking to do that. But I think it could work. And I think that for the cities, one language should be chosen. ie. English ones just have the name City, New Brunswick, and French ones just have the name City, Nouveau-Brunswick, but all of them go in both categories.