Версия ubuntu какая? Попробуй Network-manager Обновить, или удалить его и явно прописать настройки сети в /etc/network/interfaces, у меня в 9.10 бета были такие глюки.

Установи программу usergate или kerio winroute firewall, настрой как NAT либо прокси.