Help Rooted, unlocked 'Error while searching for networks' on new provider

[Lubalin]

I've been using my rooted Desire (running Redux) happily on orange for some time.

I've tried to move to a Giff-gaff contract, and so I bought an unlock code from htccode.com.

When I put my new SIM in, it unlocks fine, but then fails to find any networks, just giving a 'Error while searching for networks.' message.

I've also tried it with the O2 SIM from my work phone, and it give the same error, so I don't think it's anything to do with Giff-gaff themselves necessarily.

Any thoughts? It's driving me crazy. I've ported my number over from Orange, so now can't use the phone at all.