iPhone3G with T-Mobile Problems.

Well, I solved my own problem and I thought I would share for anyone else that experiences it.

Problem: RedSn0w updates the BaseBand when it is used with iOS 4.2.1.
It updates it to the correct version for iOS 4.2.1 (05.15.04)
Baseband 05.15.04 is NOT Unlockable.

Solution: Using RedSn0w (the same program that messed it up in the first place)
Load your IPSW and select "Install iPad Baseband".
You get a warning popup because there is a risk of losing use of GPS when you update the BB and it also makes it impossible to go back to the original BB, which obviously voids the warranty.
Boot into DFU and let RedSn0w do its thing.

Once the BB is updated to 6.15 install UltraSn0w from Cydia and your phone will be Unlocked.

Hope this helps someone.

Useful apps:
Cydia
FuzzyBand-Check your Baseband and Bootloader version.
UltraSn0w and RedSn0w.