i have not had this problem. i am pretty sure i have rebooted a few times, not just resprung. i have never seen any issue. if anything, this is way way way faster at finding tmobile than my last iphone was.
Have same configuration as you and not experiencing any problems with cellular settings. I did not restore, did an upgrade from 3.1.3 to 4.0.1 did the JB and UL .