У меня дома доступ в инет только по VPN, когда ставил beta и rc - такая же байда была, поставил систему с диска с официальным релизом - все работает.
p.s.: Кстати, для пробы попробуй поставить пакет network-manager-pptp, скачай его откуда-нибудь (с того же yandex-зеркала). В старых версиях (9.04 и 9.10) он по умолчанию не был установлен. А под 10.10 я столкнувшись с такой же проблемой просто обошелся установкой официального дистра.