It sounded so easy
Download PwnageTool 4.1.3 unlock for iPhone 3G and 3G S on iOS 4.2.1 direct link

However when I try to install my custom firmware it fails. It either gives me 1605 error or tells me I'm not eligible to activate this device. Using Tiny Umbrella to either kick out of DFU mode or just to look at my stuff I see that nothing has changed on my Iphone.

Please help! I'm in Europe but I bought my phone when I lived in the states, my phone used to be JB and unlocked by blackra1n but I fooled around with it when I heard that limera1n was out... now Im phoneless!

I'm using an iphone 3gs
Firmware 4.2.1
baseband 05.15.04-6.4_M3S2 (trying to update to the ipad baseband, wont work)
SN 85947EN23NQ

Try restoring to regular 4.2.1 on itunes. Then Install Cydia and the iPad baseband with Redsn0w 0.9.6rc7. Then Unlock with ultrasn0w if you need so.

Sounds like you aren't actually getting the phone into DFU mode. TinyUmbrella doesn't have the capability to kick a phone out of DFU mode, only out of recovery mode.

Pwnagetool 4.1 and higher will put the the phone into a special PWNED DFU mode, there is a button within the pwnagetool app to do this.