Same problem, and DFU mode did squad.
EDIT: Solved it, was a stupid "error code 1013" (so friggen tired right now I kept seeing 3101, good luck finding a fix for that). Had to delete some stuff from the host file and it worked.
Windows:
Step 1. Start > Programs > Accessories
Step 2. Run Notepad or WordPad
Step 3. Click Open.. from File menu.
Step 4. Browse to Windows/System32/drivers/etc
Step 5. In "files of type:" select all documents
Step 6. Open "hosts"
Step 7. Delete all line that has "gs.apple.com" or something like that
Step 8. Hit Save
Step 9. Restore your device
Got the fix from:
http://www.redmondpie.com/fix-itunes-error-1013-when-updating-iphone-4-to-ios-4.2.1/