Tienes habilitadas todas las conexiones? Es decir, ¿si estas por datos no tienes ningún capador de redes (tipo APNdroid) conectado?
En principio, teniendo Internet no debería haber problemas.
Si a pesar de todo te sigue sin funcionar, desinstalala y descargatela de nuevo del market, es lo único que se me ocurre.