ENCONTRE LA SOLUCION.
Susituir
Código PHP:
$base_url = "http://" . MAPS_HOST . "/maps/geo?output=xml" . "&key=" . KEY;
por:
Código PHP:
$base_url = "http://" . MAPS_HOST . "/maps/geo?output=xml" . "&key=" . KEY ."&oe=utf-8";
Lo dejo por si le sirve a alguien.