Вопрос, конечно, интересный. Попробуйте удалить сначала deb-ы
# dpkg --purge --force-depends nvidia-kernel-common-blabla nvidia-kernel-blabla nvidia-glx-blabla
и затем вызвать инсталлятор от nvidia с опцией --uninstall. Если он
откажется работать - читайте README, там написано, куда и что инсталлятор
кладет. Чистите руками. После чего верните deb-ы на место (желательно их
сразу иметь под рукой, чтобы поставить с помощью dpkg. m-a кладет
сабранные пакеты куда-то в /var/... не пользуюсь, не помню.
Остальное - с сайта, или из вашего локального кеша apt-get).