Some names I've suggested before, for the hell of it:
Communist Rome: Plebeian Republic (Instead of "Roman People")
America, vassal of Rome: Province of Canada
Argentina, vassal of Rome: Province of Patagonia
Brazil, vassal of Rome: Province of Amazonia
Generic American Vassal: Free Associate State of X
Theocratic America: State of Deseret
The Moors also need their short description changed. Unless they're vassalized by a civ with a specific name, they become "Protectorate of Moors", which is weird.