It so happens that I have a NIC that is only able to establish a connection with the current network when auto negotiation is set to false. In windows, this can be achieved rather easily by changing the NIC properties via Device Manager. Currently I am only able to do so in Ubuntu (10.04 if that matters) via the following after login:

sudo ethtool -s eth0 autoneg off speed 100 duplex full

sudo service network-manager restart

PS: I have read reports from ubuntu forums that it may be necessary to remove network-manager and only use /etc/network/interfaces for configuration, but I intend to do so only as a last resort. I would also appreciate it if someone can add auto-negotiation ethtool to the list of tags.