Just to update, I bought my UK iPhone yesterday at CPW. As expected, it shipped with 1.1.2 under which the TIFF exploit has been fixed and so standard jailbreak is not possible.
It is possible (and in fact relatively easy) to downgrade to 1.1.1 and jailbreak:
see here. You can put the phone in DFU mode, option-click as before in iTunes and feed it the 1.1.1 firmware from Apple's site. iTunes will throw an error (due to the upgraded baseband with 1.1.2), but then use iBrickr to kick the phone out of DFU mode at the end. After that, run through
the standard procedure to jailbreak and get Installer.app. You'll then have the 1.1.1 firmware with the 1.1.2 baseband. From here you can theoretically update back to 1.1.2 with the jailbreak announced on TUAW, but that's not been released yet as it needs more testing.
Now assuming that you had a US iPhone and upgraded to 1.1.2, you should theoretically be able to use the new AnySIM 1.2 released by iphone-elite to re-unlock your phone. However, if like me you have a UK iPhone then you're going to have to wait, because it looks like Apple also updated the bootloader on our phones. As far as I know, this is being worked on atm but again I'm just hanging around in IRC.
However, I did notice that the iPhoneUnlockUK site is now reporting that they can unlock native 1.1.2 UK iPhones: this was apparently confirmed over the phone. So if you really need to unlock it, then it might be worth giving them a call and shelling out the £40 to get it done.