Thanks for the response. I'm at work. We have a proxcy appliance, and although I have the passwords, it's not my area to go playing with.
I have no problems downloading the zip via IE. Seems to me that Paint.Net should be able to, too. I don't know if it's not using the proxy settings from Internet Options (okay, technically from the registry, but you know what I mean), or if it's not authenticating properly.
Which really means, I still think it's a bug