After 3 failed attempts with "error code 1004" and thinking my iPhone 4 was bricked, I finally got it to work.
I think the problem might have been a corrupted ipsw file. This all happened on my Macbook Pro - an error loop of "connect to iTunes" on the iPhone 4, and then an "error message 1004" on the iTunes of my Macbook Pro after trying to restore.
After switching to an Windows XP netbook, everything worked fine. Then I simply restored all the data from my backup on my Macbook Pro.
My guess is the ipsw file was corrupted on the Macbook Pro. Perhaps if I had deleted it, causing iTunes to redownload, things would have worked.
I was just ecstatic that the netbook made things right. Good luck to you!