Try the new phone and see - it's a shot in the dark at this point. If it doesn't work then you will need to send them an email with your changed IMEI and they'll change something on the server to allow you to unlock it.
Remember to reload your old one before you send it in!
