i just wanted to add another possible problem/solution to this thread.
i was receiving the same 1004 error on the iPhone(iPhone 4 32GB black, IOS 4.3.5, never jailbroken) when trying to run app updates and it didn't matter if it was 3G or Wifi, had no problems using iTunes on the iMac(2008 2.4ghz running 10.6.8).
after reading all the suggestions everywhere(hosts file[useless, the problem wasn't on the computer/wifi], clock manipulation[didn't do a thing], restore[didn't want to go that drastic, yet] and setting reset[didn't work]) i decided to look at my iTunes account.
turns out i had forgotten to update my iTunes account for 2 things.
a) the credit card i had on file was expired a month ago(of course, the new one arrived but i forgot to change the year on iTunes).
2) i had recently moved, and the CC on file has received that updated address, but i failed to update it on the iTunes account.
i updated both of these and now everything works.
so, for anyone still having this problem and can't fix it with the above solutions, this is another thing to check out, make sure your CC is still valid and the address info is correct. sometimes it's the little things we overlook!