Same thing happened to me... it turns out that there is a problem with the PwnageTool. Here is a note from the Dev Team's webpage about the problem:
Update #1: Theres an error in the bundle for the iPhone3GS 4.1 that prevents the new baseband from being used. If you know your way around OSX, please download the fixed bundle, and unzip it if Safari hasnt already done so. Then Show Package Contents of PwnageTool.app, navigate to Contents->Resources->FirmwareBundles and drop it there. Otherwise, please wait for the updated PwnageTool, or the OSX version of redsn0w coming soon.
Once I downloaded the fixed bundle and inserted it my baseband updated and I was a happy camper!
Good luck!