症状としては存在しないディスプレイマネージャ（gdmやlxdmなどです）を起動させようとして失敗したときのものに似ていますね。

「/etc/X11/default-display-manager」ファイルの内容はどうなっていますでしょうか。
もし、既に存在しないディスプレイマネージャを指定しているということでしたら下記コマンドを実行してみてください。（「gdm」はインストール済みと仮定しています）

sudo dpkg-reconfigure gdm

（了解です。ということで…）
こちらでlubuntu-desktopのディスプレイマネージャ（以降DMとする）である「lxdm」の線で確認をしてみました。

結果は、"DMにlxdmを使用している状態でlxdmパッケージを削除すると、「/usr/sbin/lxdm」と記述されている「/etc/X11/default-display-manager」ファイルを書き換えずに去ってしまう" ということで、これによりDMが起動されなくなることがわかりました。
（おそらく、kenken92さんはこれを踏んでしまったのではないかと…）

原因はlxdmパッケージのパッケージメンテナーのミスで、メンテナースクリプト「lxdm.prerm」に記述されている「DAEMON=/usr/bin/lxdm」が間違ったものを指していることにあります。本来は「DAEMON=/usr/sbin/lxdm」でなければなりません。

これの解決方法は、#2では「dpkg-reconfigure」を提示したのですが、この件に関しては条件が合わず修復できなかったりしますので（他にも切り替えできるDMをインストールしているという場合は可能ではありますが）、対策は「default-display-manager」ファイルを手作業で直接書き換えるということになりそうです。（以前に使用していたDMの情報が「default-display-manager.dpkg-tmp」というファイルに置き換わっていると思いますので、それを参考にすると良いと思います）