Did you find a solution to this?
My girlfriends phone is doing the same thing.
Tested the sim in another phone and it worked fine. The phone can see the network exists when you search available networks, but then won't connect.
Orange UK in this case.
Let me know if you got to the bottom of this issue and whether it is even the same thing.