No es necesario la tarifa de datos, al menos para que te detecte la señal gps y según sea quizá para coger los mapas etc... si que necesite conex de datos.
¿Estás dentro de casa? Si es así seguramente por eso que no te pille. Si lo has probado fuera... espera un poco porque la primera vez tarda en pillar...
¿Conoces Gps Status? también estaría bien que te lo instalaras(esta en el market) para ver si te pilla señal y de cuántos satélites antes de meterte en ningún programa.