Muchisimas gracias por la respuesta, pero creo que el problema esta en la ROM que tiene mi telefono (la de movistar). Eso puede dar problemas, porque no puedo descargar datos a traves del GPS Xtra por ejemplo y quien sabe si afecta tambien al modulo GPS.
Voy a cambiarle la ROM por una oficial de Samsung y probare a ver que tal va la cosa.