The only thing that immediately comes to mind is that some network admins like to force speed and duplex on their switches, disabling ethernet negotiation. But if the NIC isn't also forced, it defaults to 10/half, which still causes problems, unsurprisingly.

If you can get ahold of your net admin, have him check the ports you're plugging into to see if they are forced to something. If so, have him turn negotiation back on, or, failing that, force your cards to the speed the switch is forced to. (Under Linux, that would be done using the "ethtool" utility.) If you can't get a net admin to tell you, just try forcing your NIC to each possible setting and see if any of them work. If they are forced, they're likely to be forced to 100/full, so start there.