I had a similar problem with my Gmail. I could receive emails, but not send them out.
It was resolved by me re-setting up my email, following the directions
here to the letter. Once that was done, no more problems. You may want to try this out if you've already ensured you have the correct settings in GMail.