Risposta forse banale... ci saranno dei disservizi momentanei con google?
Perché exchange lo usi da tanto tempo ma se i problemi sono iniziati da poco, senza motivo apparente, potrebbero esserci casini nei server di google.

Comunque prova a modificare la password dell'account, una volta avevo dei problemi con gmail e si sono risolti per magia cambiando la password (mettici anche simboli e numeri).