I have the exact same problem. It started yesterday afternoon (2010-01-9). I have tried selecting only GMS and Automatic or manual network selection. And diffrent SIM-cards from diffrent service-provider (my phone is not operator locked). Didn't work with any SIM-card.
I think this might be a firmware issue. I'm running version 3. I havn't tried upgrading to the latest firmware but will do so today.
Everything else, from GPS to WLAN is working just as it should.
Using *#7370# 12345 to reformat the phone did not either help. It still only says "SIM card registration failed".
SIM card placement, and connection pins are all great. I also tried starting the phone without the memory card, but to no luck.