Earlier we discussed how to unlock iPhone on iOS 4.0. In this tutorial we will outline the similar steps (as jailbroken iOS 4.0.1 is 
technically iOS 4.0).
To be able to unlock your iPhone on iOS 4.0.1 you first need to jailbreak it.
Once it’s jailbroken, proceed with these simple steps to unlock your iPhone 3G to be able to use any carrier sim card.
1. Run cydia on your iPhone 3G
2. Goto search option on right bottom
3. Search for ultrasn0w (its zero, not O) – it will be version 0.93 [there is no need to add repo666.ultrasn0w.com to cydia, as it is already included in the redsn0w 0.9.5 beta 5 build 5]
4. Install ultrasn0w version 0.93 from cydia
5. Restart your iPhone and voila!
This will unlock your iPhone 3G to use any cellular network provider sim and not only your default carrier (Which is AT & T usually)
Have done exactly what you said to my 3G IOS4.0.1 (The only difference is that, instead of ultrasn0w version 0.93, 1.1-1 is found when I did the search.) Put my TMobile SIM card in and No service. Used my friend’s AT&T SIM card, no service neither. Please help. Thanks in advance.
did the unlock process complete successfully?
Guys, never ever updte to IOS 4.1.2, i got screwed up, i upgraded ended with locking my phone to limbo, it took me three days to jailbreak my phone and downgrade back to 4.0.1 (which is so far the best) and restore my phone.
thanks a lot
glad to know that you finally solved the issue