No he tenido ese problema. Soy de Vodafone. En todo caso, no debería ser ninguna limitante el cómo te estás conectando a GMail: el solo mira que estés conectado. Al estar probando una que otra ROM, hay alguna que te da la oportunidad al inicio del proceso de conectarte via WiFi, con lo que haces toda la configuración por esa vía; hay otras ROM con las que tienes que hacer todo via 3G, y en ambos casos me ha funcionado todo bien.
Lo único que se me ocurre pensar es que tengas alguna limitante con la conexión WiFi.