What the hell?!

[la79]

Alright I can't for the life of me figure out what is wrong. I have been unlocking and using iphones since good'ole 1.0.2. So I am well aware of the unlocking scene...

Anyway this is my problem. I have an Iphone 3G that I haven't been able to unlock. It currently is on ios 4.0 baseband 05.13.04. I am using Ultrasn0w 0.93. To Jailbreak it I'm using the newly released redsn0w 5b5-4.

The problem is I keep getting "searching..." and the phone will not say "iphone is activated."

I have never been able to unlock the phone even when it was on 3.1.2 and I was using blackra1n and blacksn0w. I thought the new release of ultrasn0w would solve my problem.

The phone was given to me by a friend. His contract ended and he went to another provider. He did not give me the Original ATT SIM but I went to the ATT store and was given a new sim. Could this be the problem? Since I don't have the orginal SIM? But shouldn't redsn0w hacktivate it?

I know the problem is not hardware because if my girlfriend uses her sim in the phone it will work fine. It's just the unlock and after I reboot the phone. I do also still get the "waiting for activation" screen.

Anway I have an IPhone 3GS on 4.0 which I activated and Unlocked fine and is on Tmobile USA. I had no problems here at all.

Advice?

Anyone have any advice?