Después de mirar las dos soluciones propuestas en este foro y ver que NO me funcionaban, hice otro método, no sé si está explicado ya, y por fin, me ha funcionado.
Fui al ftp de mediatek: epo.mediatek.com
El login de este ftp es:
usuario: epo_alps
pass: epo_alps
Una vez ahí descargas los archivos (solo me funcionó con safari, google chrome no me bajaba los archivos).
Una vez ahí descargo los archivos que hay dentro y los meto (creando yo la carpeta ya que en mi neo premium no venía por defecto)
/storage/sdcard0/data/misc
ahí pegas los archivos que hay dentro de la carpeta que os habéis bajado.
Una vez hecho este paso, entráis a la APP Mobileuncle Tools, Modo engineer, Modo enginer MTK, pestaña Location, y en Satelites dejáis el GPS encendido y dejáis el teléfono al aire libre (terraza o similares). Así me funcióno ya que me ha encontrado TODOS los satélites europeos, ahora ya no tengo problemas.
Funcionan programas como google maps, runtastic, endomondo y otros similares. Espero que os ayude.