Same problem here. I'm on ios version 5.1 using Gevey (blue) with a preserverd baseband of 2.10.04 (hoping for eventual software unlock!). I've noticed that the problem only surfaces after I have rebooted my phone, and the Gevey does its own unlock. Your'e right about the problem relating to 3G - incoming calls are fine with 3G off.
I found the fix was
a) go into Settings, then phone, then Sim applications, then reset the Gevey.
b) Click Ok when the popup gives you the Gevey instructions. Wait 10 seconds for it to drop off the network. Dont do anything yet.
c) Go through the steps manually like you did the first tiime -Dial 112 Bla Bla Bla.
d) when it finds signal, you'll have incoming calls with 3G switched on (until you reboot the phone again!!).
It's a pain in the arse. I have a suspicion that it relates to the baseband, as I had the same problem on Ios 4.3.3 bb 2.10.04. Was hoping it would be fixed on Ios 5, but it wasn't.
Also think that changing to baseband to 4.10.01 (restoring down to Ios 4.3.3 with stock firmware, then back to Ios 5.1 with baseband preserved) might help. The reason for this is that I havnt read about this problem much, and suspect that if it existed on all baseband versions, the web would be full of forums discussing it.
I am having the exact same problem and I am on rogers as well. However, when I go into Settings > phone, there is no "Sim Applications" category that can be selected and therefore I cannot reset my gevey.
Does anyone else have an idea about how to fix this. I have restored iOS 5.0.1 twice and have tried popping out the Sim+Gevey multiple times.