I noticed 3 messages stuck in my Gmail outbox post-OS 2.2 upgrade. Just sitting there. Mocking me. "Sending" but never getting "sent". Following a comment by Matt, I re-typed my password and voila, the intertubes they were cleared.

Not sure if this will work for everyone, either by itself or with a reset, but give it a try and let us know.

UPDATE: scottb helps out earnie in the comments with a Google link for unlocking display Captcha to overcome an invalid sender address problem. Our readers rock!

Any other trouble-shooting tips? Keep 'em coming!