I have a similar problem, I have bought a locked iPhone 4 32gb from the US (I'm using it in Greece currently) in the summer, I have the 4.0 iOS, baseband 01.59.00 and jailbroken. For the last days, several times the phone gets the no service message or sim failure, I have to either switch on and off the airplane mode, or to reset network settings or to hard reset to make it get a signal. Do you know what is going on? The problem has occured only a couple of times since I got the phone but not so often as the last 2 days.
Thanks for the help!