Returning legacy player - cannot locate character

[Enkidoh]

Can you remember what server your Legacy character was on? A good way to find out is to log into your account on the Mogstation and it will show all characters attached to the account, along with the server they're currently on. Armed with this information, you then have to find what 'data center' group your server is now a part of (in the 2.1 patch servers were grouped into 'data centers' which you select on the main title screen - doing so will only show the servers attached to that specific data center on the character screen, so it's possible you're just set for the wrong data center at the moment), and then set it accordingly.

Unfortunately I don't have a list of what data center has what servers at this time, but I'm searching so just bare with me.

EDIT: finally found the list buried in the 2.1 patch notes, so I'll copy and paste it here:

Elemental
Aegis / Atomos / Carbuncle / Garuda / Gungnir / Kujata / Ramuh / Tonberry / Typhon / Unicorn
Gaia
Alexander / Bahamut / Durandal / Fenrir / Ifrit / Ridill / Tiamat / Ultima / Valefor / Yojimbo / Zeromus
Mana
Anima / Asura / Belias / Chocobo / Hades / Ixion / Mandragora / Masamune / Pandaemonium / Titan
Aether
Adamantoise / Balmung / Cactuar / Coeurl / Faerie / Gilgamesh / Goblin / Mateus / Midgardsormr / Sargatanas / Siren / Zalera
Primal
Behemoth / Brynhildr / Diabolos / Excalibur / Exodus / Famfrit / Hyperion / Lamia / Leviathan / Malboro / Ultros
Chaos
Cerberus / Lich / Moogle / Odin / Phoenix / Ragnarok / Shiva

Also note that 3 extra servers were also added after that when the PS4 version was launched: Shinryu (Mana server group), Jenova (Aether server group) and Zodiark (Chaos server group), but these are 'new' servers that you cannot transfer an existing or Legacy character to at this time.

Hopefully this has helped.