"Could not activate cellular data network"

My microSIM has worked fine in my iPad 2 for a year. The iPad 2 was bought, subsidised, in the Orange Shop in March 2011.

I got the new iPad on release date, full price from Apple Store. I put my microSIM from my iPad 2 in it, and got the error message "Could not activate cellular data network", even though it's showing "Orange" and 4 bars in the top left.

If I turn the iPad off then on, it starts working, and will work fine for hours, then the problem starts again, forcing another reboot to fix it.

I phoned Orange who confirmed it should work, and there's no problem with my account, and they can see my devices all connected to the masts.

I did a full restore in iTunes of the new iPad, and set it up as a new iPad. This didn't fix it.

Yesterday I took the new iPad back to the Apple Store and they swapped it for a new replacement one. Same problem.

Any ideas?

Thanks.