There appears to be something going on with Gmail’s SMTP ports since the issues they had at the start of the week. How does Gmail going down make BBC Lunch time news?
Ref: Blogoscoped forum article
This link solved the problem for me. Some GMail help articles state you should use port 25 or 465. As previously discussed O2/Be broadband in the UK doesn’t let you use Port 25 for anything other than O2 Email. I was using 465 which is Secure SMTP (with SSL). However, GMail now (appears to) require port 587: Message Submission (with TLS).
Peasy.
— update
Experiment with turning off your SSL setting as well!