Yeah, mine is doing the same thing.
I have a 8300 with 4.5.0.52 on AT&T in NYC.

I can send using one of my gmail accounts but when I try to send with or to the other, it initially gives a checkmark and then turns to the red x, and when I click on it, it says Message included an invalid address.

I tried a battery pull, deleting the account and re-adding it under BIS, deleting and resending service books, but nothing seems to work. I can receive emails on my blackberry though if I send something to that email address through the computer.

Also, since I just switched to another curve on friday (my last one broke), I have been having trouble getting emails sometime and when I log into AT&T BIS, it asks me to enter the PIN and IMEI and after that, it seems to work ok.

It's such a weird error to not be able to send to only one of my gmail accounts.