I'm having this exact problem, very annoying since it's never even been jailbroken. The only non-official thing I've ever done with it was install the 4.1 (or 4.2) GM a few days before the release. I had to use TinyUmbrella back then to get it working and updated, and seem to recall having to resort to that gs.apple.com fix.
Tried everything now, even tried going back to 4.2.1 but no luck. Very pissed off indeed, gonna give up for tonight, and I hope some kind soul will offer a solution when I get up tomorrow
I thought I may have stumbled across a fix in the latest TinyUmbrella - there appears to be option to fix the 10XX issue specifically by entering DFU mode, then using "Fix Recovery" but it's always greyed out. *sigh*
Wish I'd never even bothered, especially now it looks like the ****'s at o2 are charging for personal hotspot - they want me to pay EXTRA for their pathetic 3G coverage, which I already could have done via tethering? They can **** right off, moving carrier when my contracts up, I;ve had enough of them.
edit: Just to clarify, I've tried restoring every which way, rebooting, different usb ports, that gs.apple.com thing, pfffffft!