One of my friends in the UK sent me an email from his Gmail account and I noticed that he had a email@example.com email address instead of a firstname.lastname@example.org one. I went to www.googlemail.com and saw that it redirected to Gmail.
At first I thought that a email@example.com email address will be different from a firstname.lastname@example.org email address (for example, if email@example.com works, then firstname.lastname@example.org will not work). But later I sent a test email to my own Gmail account using googlemail.com instead of gmail.com and it worked.
I googled a bit (of course :)) and found that Google has problems with the Gmail trademark in the UK and so they are using the googlemail.com address instead of the gmail.com one. More information about this is here and here (cached).
Maybe, this website (www.gmail.co.uk) is the one they are problems with???