iPhone 4 Activation Required on every reboot.

Hello, i have an iPhone 4 iOS 5.1.1 BB 04.12.01 not jailbroken or anything, fresh update and restore to newest firmware i using on Official Carrier. iPhone works great when on, but every time i turn off or restart phone goes to Activation Required and then Connect to iTunes screen, iphone get Searching... then No service.

if plug on computer Itunes show a message that canot connect to iPhone and need to be restored.

i have to restart three or four times the iPhone to recognize my carrier and then get the screen to the activation over WIFI (where detect your wireless networks), this is the only way to get it to work.

have this happened to anyone here ? any solutions ?