A couple of weeks ago I bought a refurbished iPhone 3GS from the Apple Store. They activated it in the store with my Orange SIM.

When I got home, I updated to 4.3.3 firmware. All was working great. Yesterday, the GPS was playing up, so I restored it with iTunes.

After restoring though, I got this message in iTunes:

...almost like the phone now has a carrier lock! I'm baffled - it was working fine with this exact same SIM before I restored. Would this be to do with how it was activated in-store?

It's completely stock, not jailbroken or modified in any way. I'm going to take it back to the Apple Store next week if there's no solution.

Thanks for any help.