Hola! Pues a mi me pasa algo similar pero he logrado resolver el problema.
Lo mío consistía en que las aplicaciones como el navegador, Tuenti o Youtube me decían que no había conexión (aunque estaba conectado y transfiriendo datos), pero en el caso del navegador y Youtube accedía a las funciones sin problema, no siendo así con Tuenti o Búsqueda por voz.
Desde entonces lo que hago es lo siguiente: con Extended Controls y Task Killer, antes de desconectarme de la red (ya sea por wifi o 3g) mato las aplicaciones que usan la red, así "no se dan cuenta" de que se han desconectado, y simplemente, cuando las quiero volver a usar lo hago siempre una vez conectado, y no tengo problemas de que digan que no hay conexión a internet cuando no es así.
Por resumir, el quid de la cuestión está en que nunca debes desconectarte cuando una aplicación está haciendo uso de internet, ciérrala antes.
Espero haberte ayudado
