Vete a "Ajustes" -> "Ajustes adicionales" -> "Región" y cambia a Andorra por ejemplo. Entra de nuevo a la aplicación del tiempo y revisa si ya te ubica.
No sé si estará bloqueado el acceso a la ubicación en la aplicación para España por algún motivo o es un error...
Lo que no me he fijado de momento es si se va actualizando si vuelves a cambiar a España como región.
Un saludo.