I've gotten past Utira Town and used the Pokemon Center there, but my Gardevoir can only teleport to Helios
I ran into this on 1.1.6 and tested a bit:
Teleport will only bring the player to cities up to Helios (Telnor - Helios). Out of those the player is transported to the one they last healed in. Healing in any other city (Utira and further on) won't change where the player teleports to.