I have the same trouble with the Nexus 1 - most of the time it is in Emergency Calls Only, I thought this was due to living in poor reception area, but I have this in the centre of Bristol, Bath, and London! It has had a software update and been back to the manufacturer, but still has the some problems. It comes to something when I actually miss my old Nokia "brick". Vodafone keep telling me that they have no information about trouble with other Nexus phones, but I have to say I just don't believe them. I basically pay all that money to have a phone that cannot receive or send calls or texts, let alone use the net! As soon as I can I will shift mobile suppliers - NOT HAPPY!
I've had this quite a bit.... Got my first Nexus One last May and the problem started in September. I then got a replacement and it's started again. I've put the SIM card into other devices and had it work perfectly so it's not a netwok issue in my case. I'm now getting my third Nexus in 11 months. Really annoying.
One thing that sometimes helps is putting it into airplane mode and then taking it out.