Měl sem stejněj problém, přechodem na novou versi nějak zkurvili kódování.
Kamarád mi poradil že snadné řešení je jít do nastavení a dole v General (cz: obecné?) je možnost "Outgoing message encoding" (cz: kódování odchozích zpráv?). Přepněte z "default" na "Unicode (UTF-8)"
Nevyřeší to sice problém s příchozími maily, ale ty už nějak přečtete, podstatné je že odchozí maily nebudou zprasený a nebudete tak sami vypadat jako blbci :)
Jinak na nějakym gMail fóru to už řešili a na nápravě se už nějak dělá, ale moc sem to nesledoval