Necesitas tener las Pokedex Nacional para que evolucionen los Pokemons de otras regiones en Fire Red.
No se la razón, pero ese es problema...
Cuando no tienes la Pokedex nacional, solamente evolucionan los Pokémon de Kanto.

Tienes que activar la Flag "829"
y luego tienes que usar el "special 0x16F"

Suerte
y
Saludos!