I have not used Quickpwn or yellowsn0w on a 3g before, how I usually do it (and will probably fix your problem) is restore the phone to stock ios through iTunes then jailbreak with Redsn0w (and flash iPad 06.15.00 baseband if needed) to the device.
Once the Jailbreak is done, launch cydia and let it update (you will need to either turn off the screen sleep in the settings or make sure the screen doesn't go to sleep while updating). The reason for this is the 3G is a slow iphone (compared to today's standards) and the cydia update doesn't seem to run in the background when the phone screen is in sleep mode (atleast thats what i have found. Once it's updated, search for Ultrasn0w in cydia and install it, reset phone and your phone should be unlocked and on the 4.2.1 software (latest software available for iphone 3G)
Keep in mind that if you update the phone through iTunes, that may update the baseband. If you want to retain the baseband, use the option to make a custom ios through redsnow before you update the iphone. A good website for iPhone jailbreak info is www.redmondpie.com or whack the word redmondpie in google alone with your search term ie. "iphone 3g jailbreak 4.2.1 redmondpie"
I thought i would post a reply just to get the ball rolling for ya ;)