It does seem too difficult to get the title, at least judging from all the anecdotes. It's something that needs to be adjusted for future versions.

Replacing and retraining have no effect, and can have no effect, on traits of any kind. The same goes for fighting an enemy captain or general. You do need to fight one of the factions for which you can gain a triumph, however (you can't become "Imperator" from fighting rebels). Upgrading from .73 to .74 shouldn't have prevented you from gaining the title.