Q1: Is your new phone compatible with your old purchase?
Example:
Yes: You bought the game from the Apple store, and your new phone is also an Apple phone.
No: You bought the game from the Apple store, but your new phone is an Android market / Google phone.
If Yes, move to #2.
If No, than stop. You have to make a new purchase of the game as Apple and Google don't share purchases.
Issue: Your current phone must be the same Phone Overlord Company as the original purchase.
Q2: Are you logged in properly, accounts linked properly? Etc?
Follow the devices / Phone Overlord Company link accounts, restore purchase procedures (including restarting devices and forced logouts).
If No, than do so. That should cause the phone to automatically update correctly.
If Yes, okay, this might be an issue with the EK.
Send device infor for the old phone, new phone, and where you go the game.