One of my friends in the UK sent me an email from his Gmail account and I noticed that he had a firstname.lastname@example.org email address instead of a email@example.com one. I went to www.googlemail.com and saw that it redirected to Gmail.
At first I thought that a firstname.lastname@example.org email address will be different from a email@example.com email address (for example, if firstname.lastname@example.org works, then email@example.com 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???