I don't know what your address currently is, or what you tried to sign in with, but you'd be best making sure your gmail account is set to use @googlemail (check on via the web interface) and signing in with @googlemail.
That switch to @gmail for UK customers has screwed up a lot of people's phones. (I'm not sure why they bothered with the switch, I've handed out my @googlemail address to people as @gmail and have always recicved everything just fine, as far as I'm aware).