Carrier Unlocked iPhone locked after restore

Hi All

I had my Iphone unlocked via my carrier, vodafone UK, and have been happily using a Three PAYG sim for a number of month, however im due to go to the genius bar on monday and thought i would back it up and restore it so im ready, im now getting this message:

The SIM card inserted in this iPhone does not appear to be supported.
This iPhone is not currently setup to work with carrier you're attempting to use. Please insert another SIM card from a supported carrier or request that this iPhone be unlocked.

Ive restored twice now, once normal and once DFU mode and still getting the same, i have proof that it should be unlocked in an email from the Vodafone NUC resolution centre

It was jailbroken BUT it was officially unlocked and not software unlocked.

Obviously now i cant activate it as i dont have the original vodafone sim card!

anyone got any suggestions on what i should do?

Thanks

 

Vodafone are no help, all the imei checking websites show it as unlocked so I don't know what's going on

 

This is now getting stranger, tried a vodafone sim, orange sim, Three sim and none activated it, tried a t mobile sim and it has activated and locked to t mobile, its never been on T Mobile, not even as a PAYG, its only ever had vodafone, orange and Three sim cards in it, going to restore it now and hopefully that fixes it, if not maybe apple can do something when i have my appointment with them on Monday