Well after a lot of trouble I have finally gotten my iPhone unlocked. I've tested it with two Australian networks, Optus and Telstra. Both worked perfecly!

Everything is works too including iTunes syncing, Wi-Fi, YouTube etc.

I bought my unlock from http://iphoneworldwideunlock.com/ and I highly recommend them! The service was super quick and the unlocking process was so easy even for someone like me who is somewhat technically challenged.

I also found something else out today, after all this trouble unlocking my iPhone to be used in Australia, I'm now moving to Los Angeles next month where iPhone's already work! :p Oh well, 4 weeks of use in Australia is worth the time and the $50.