Alas, that particular error has a bazillion things that can cause it. When I first started a few months ago, it was usually caused by choosing the wrong board - there's both a Duemilanove 128 & a Duemilanove 328 and picking the wrong one causes that error. But you said you read the other messages, and had the right board picked, so I figured repeating it would be useless. Plus, it doesn't seem to happen anymore since IDE-16 came out. Yea!
Try hitting the reset button on the arduino at random times, both before and after clicking the upload button (ie, try uploading several times, hitting the reset only once each time).
I assume you've seen this page: http://arduino.cc/en/Guide/Troubleshooting#toc1
FWIW - I use Zone Alarm, and it works fine for me.
Any chance you can borrow an Arduino from someone else and see if you can upload to that one?