De entrada cálzale un soft reset. Ya sé que lo habrás hecho, pero otra vez. Luego salte a la calle a cielo abierto y ponte a esperar. La primera vez tarda bastante. Incluso más de 10 minutos. Casos de hasta más de 20.
Para acelerarlo descarga el XTRA que es la posición de los satélites. Hazlo via wifi para que no te cobren por la conexión. Te cogerá más rápido los satélites.
Por cierto, qué navegador has instalado? tomtom, igo, ...? Dime y dime qué configuración llevas puesta del gps tanto en tu omnia II como en dentro del navegador.
A mi, el gps, también es lo que me da más quebraderos de cabeza. Mi antigua trini cogía mejor los satélites. Ánimo y ya me cuentas