Just got over my fears and updated the firmware from my iPhone from 1.1.2 to 1.1.4.
I used the Installer.app tool that was already on there to install a program (read from step 5 on this page) to check which Baseband firmware I had (v3.9).
I then used Option Click on the iTunes restore button and gave it the iPod 1.1.4 firmware file I had previously downloaded.
The iPhone updated and rebooted – of course it was locked and needed activation.
I quit iTunes and then basically followed the guide at http://www.hackthatphone.com/114/iphone_iliberty_mac.html and it was all pretty easy.
After a couple of minutes – 1.1.4 unlocked Joy 🙂
Next was to localise it with Australian phone formats etc. Add the source wpool.com/iphone to Installer.app and install the localisations for 1.1.4 (all three of them) and reboot the phone. On telstra I now get a nice pretty Telstra Logo.