gdmはGNOME用ですが、KDEを起動することもできます。UbuntuにKDEをインストールした場合は、gdmが使われるんじゃないでしょうか。


で、複数の問題が絡んでいるかもしれませんので、それぞれの対処方法について書いておきます。

1. KDEに必要なパッケージを削除してしまったかもしれない。
普通にインストール・アンインストールを繰り返している場合はそういうことは起こりません。ただし、例えばサードパーティのリポジトリを利用したり、debファイルを強制的にインストール・アンインストールを繰り返すと、依存関係が壊れる可能性はあります。で、Kubuntuに必要なパッケージ一式をインストールしたいのであれば、「コマンドモード（おそらくコンソール画面？）」でログインし、
sudo apt-get update
sudo apt-get install kubuntu-desktop
sudo reboot
を実行してください。上から順にパッケージ情報の更新、Kubuntuに必要なパッケージ一式のインストール（すでにインストール済みのものは除く）、再起動を行うコマンドです。


2. ビデオドライバをvesaにする方法
同じく、「コマンドモード」で
sudo nano /etc/X11/xorg.conf
とし、「Section "Device"」あたりに「Driver "vesa"」を追加します。例えば、Deviceセクションの部分は環境に依存すると思いますが、以下のような感じになるかと思います。

Section "Device"
    Identifier     "Configured Video Device"
    Driver         "vesa"
EndSection

もし既存のDriver行がある場合は、そのドライバ名をvesaに変える感じで。保存はCtrl+O、終了はCtrl+Xです。やっぱり
sudo reboot
で再起動を行うと、vesaドライバで起動するのではないでしょうか。


3. ログイン画面をkdmに切り替える方法。
kdmがインストールされていること前提で、Ubuntu Weekly Recipeの第6回が参考になるでしょう。