If the iPhone was UPGRADED to 1.1.2 (meaning it still has 3.9 bootloader), you can re-unlock it by downgrading to 1.1.1, jailbreaking with jailbreakme.com, installing OktoPrep, upgrading to 1.1.2, using touchfree jailbreak, installing anySIM 1.2.1u, putting iPhone in airplane mode, and running anySIM 1.2.1u while the iPhone is in airplane mode (the airplane mode part is extremely important, you WILL brick the phone if you attempt an unlock on 1.1.2 without airplane mode).
If the phone came with 1.1.2, you're SOL though...as those phones have the 4.6 bootloader, which blocks all current unlocks. Wait till a week or 2 after 1.1.3 firmware launch, and see what happens (and DON'T update in the meantime).