Basic Amazon S3 Setup
I did end up opening a support ticket with Craft- they immediately suggested that this could be caused by a firewall. To which I scoffed! But after talking with some other folks in the office, this seems to be the case.

Unfortunately we never found a firewall solution to this problem. What did work was to assign a static IP to my computer that bypasses the http-proxy packet filter.

So yeah. Firewall. Dang.