Is it possible to get unlocked US purchased Iphone working with Telecom NZ?

I have an Unlocked Iphone 3G that I have been trying to get to work on Telecom here in New Zealand. The phone was purchased by me 11 months ago in United States from Carrier AT&T. Three weeks ago, I installed Iphone Update 3.0. Last week I restored my Iphone, installed Redsnow 0.7.2, then through Cydia, I downloaded and installed Ultrasn0w. I put in my old Optus SIM card (from Australia) to test it and it read it just fine, no problems.

Then a couple days ago, I went to the Telecom store and purchased a Prepay cellphone phone plan. The girl who installed the SIM said it would probably take a couple hours for the Network to kick in. I waited half a day and still no Telecom bars, which worried me. I looked under the 'About' settlings>Network and the phone was reading ‘Telecom’. I looked under the phone settings and the phone registered no number, which I found curious. Still I downloaded and installed the Telecom XT Carrier Bundle to see if it might make any difference. Of course, it didn’t and the Phone still showed no signal bars.

The following day, I went over to the same Telecom retailer and asked them to take a look at the SIM to verify that it was not faulty. The store clerk went ahead and put it into SIM in another phone. Sure enough the SIM apparently worked just fine in the other phone. I asked if she had any ideas and she admitted that she "didn't have very much experience with the Iphone and recommended that I just try reinstalling the software. So now I’m asking the forum community if you all have any ideas about any possible fixes? The only thing I can think of at the moment reinstalling all of my software and re-jailbreaking and unlocking the phone. Is it impossible use an unlocked US purchased Iphone here in NZ. Anyone have any anecdotal evidence? Note: I have tried with 3G both off and on and I have tried restarting several times.

*Posted this on geekzone forums too put wanted to add this here to see if I got any different responses