Ура!!! Заработало! NAT работает!
Огромное спасибо за поддержку, помощь и активное участие в решении проблемы Alsvartr'y, Alan'у и остальным.
Понадобилось мне тут ещё squid настроить.
Установил, настроил по докам с этого форума:
apt-get install squid
И вот это в конфиге прописал..
http_port 3128
cache_dir ufs /var/spool/squid 100 16 256
acl our_networks src 192.168.0.0/24
http_access allow our_networks
visible_hostname server
/etc/init.d/squid restart
И нифига не работает прокси с компа 192.168.0.2
Что ещё нужно, поиском прошёлся по forum.ubuntu.ru не нашёл других настроек.
P.S: прошу прощения за небольшой офтоп, просто не хочеться отдельную тему создавать и заново описывать как у меня сеть настроена.