The problem you are having here is indeed the network-related. I have a similar situation at my unversity, but since i study these things i can give you the answer.
It's the firewall. Your network administrator chose to block everything but the few common TCP ports - a fairly common (and wise) security practice. Android market operates on TCP/UDP ports 5228, which are not commonly used ports, thus the downloads get blocked by the firewall (the market works fine but the apps won't download). What you can do is to ask your network administrator to open up specifically these ports to allow Android market to work.
So no hard-reset or newer phone versions will help (unless Google decides to transfer Android market to port 80, 443 or any other commonly used port).