Whenever an 'enter password' message box pops up on my iPhone I immediately enter my iTunes password, it's pretty much a an immediate action and I don't tend to look at what the message is saying once I see the word: 'Password' I just zone out and enter it.
So when the familiar message box below popped up I proceeded to enter my iTunes password as per usual!
The main problem here was that it wasn't asking me for my iTunes password but in actual fact it was asking for my GMail password for the push Email notifications I receive from my account.
By entering my iTunes password obviously this was wrong and the message box kept reappearing, after a couple of incorrect attempts I suddenly realised I needed to enter my GMail password! So I did.
Unfortunately this didn't seem to work either and the message box popped up yet again, and again, and again - I checked the password I was entering was actually correct and still I got the error. After a couple of unsuccessful attempts using the GMail password I then thought I may have been locked out of my account, checking online I could easily access my account with the same password I was using on the iPhone. The plot thickens.
After doing some research I found a solution: the problem is that if you enter your password incorrectly a certain number of times then Google (and any other sensible system) will think that it could be a potential attack by an automated system or evil spam robots. To counteract this automated attack a CAPTCHA is usually displayed, only on the iPhone you can't see the CAPTCHA form!
Simply go to the page: https://www.google.com/accounts/DisplayUnlockCaptcha - enter your password and fill out the CAPTCHA!
All should then be well on your iPhone and you can receive all your emails yet again!
I'm not sure why the error message came up in the first place, it could have something to do with the move from googlemail to GMail in the UK but I'm really not sure!
Sources: Google Support Forum Thread