Pues mira que casualidad, que andaba buscando información sobre éste problema.
Mi teléfono Galaxy Nexus libre de origen, con el operador Movistar, la sincronización activada, me llegan las notificaciones tanto a través de la aplicación Gmail (lo tengo todo marcado: notificaciones y sincronización activada) como desde la aplicación K9-Mail (para mi el mejor gestor de correo de android) aunque luego vas a cuentas y sincronización y te pega un error cuando fuerzas a hacer la sincronización manual.
El teléfono de un amigo: Galaxy Nexus bloqueado por la operadora Vodafonde y de serie: recibe las notificaciones a través de K9-Mail pero no las recibe a través de la aplicación nativa Gmail.
Tampoco puede hacer llamadas de voz y vídeo a través de GoogleTalk o a través de Google+ sobre 3G e incluso tampoco le funciona el reconocimiento de voz de Google a través de los datos móviles y sin embargo yo no tengo ningún problema.
Sospecho que el problema está en el APN que va a través de un Proxy de Vodafone y que tiene algunos puertos capados.
En el foro hay un hilo de un usuario que tiene el problema del reconocmiento de voz y da las instrucciones para cambiar el APN
http://www.htcmania.com/showthread.php?p=3897080
A lo mejor os puede servir de ayuda!
Un saludo
