Account-wide titles not so Account-wide

So..I have this old title Corporal on this old rogue and my other toons don't have it. What gives?
Do they have to be on the same server?

Not all titles are available to use account wide, PvP titles being one of them. There are exceptions that apply to mounts as well (in particular a couple of PvP mounts.)