De vez en cuando recibo una llamada de un cliente mío que se queja de esto. No tengo idea de una solución real (o cuál es el problema real) pero generalmente recomiendo hacer lo siguiente en orden:

1. Cerrar por completo Mail: toca dos veces el botón de inicio, desliza hacia arriba en Mail
2. Reinicio normal: presiona y mantén presionado el botón de encendido hasta que aparezca la opción de apagar, espera 30 segundos para que se apague, presiona y mantén presionado el botón de encendido hasta que aparezca de nuevo el logo de Apple.
3. Intenta de nuevo y si falla, reinicio forzado: presiona y mantén presionados el botón de encendido Y el botón de inicio hasta que se apague - sigue manteniéndolos presionados hasta que vuelva a aparecer el logo de Apple.
4. Elimina y vuelve a agregar la cuenta de gmail.

También tuve este problema y no tuve suerte al eliminar/cerrar cuentas y reiniciar mi teléfono como sugirió @Harv. Afortunadamente, recibí ayuda del equipo de soporte de G Suite de Google y me ofrecieron una solución que funcionó para mí:

• Agregar la cuenta como una cuenta de 'Exchange'
• Establecer el servidor como m.google.com (dejar el campo de dominio vacío).

La razón subyacente de esto (y las instrucciones más detalladas) se abordan en este artículo de ayuda de G Suite.