Deve ser tão fácil quanto dizer ao apt que você deseja remover o Xorg e ele irá desencadear a remoção de todos os pacotes que dependem do X.
sudo apt-get remove xserver-xorg-core
Para o caso de não funcionar, aqui está uma lista de tudo o que o ubuntu-desktop dispara para ser instalado na instalação do meu ubuntu-server:
account-plugin-aim account-plugin-facebook account-plugin-flickr
account-plugin-google account-plugin-icons account-plugin-identica
account-plugin-jabber account-plugin-salut account-plugin-twitter
account-plugin-windows-live account-plugin-yahoo acl acpi-support acpid
activity-log-manager-common activity-log-manager-control-center
adium-theme-ubuntu aisleriot alsa-base alsa-utils anacron apg
app-install-data app-install-data-partner appmenu-gtk appmenu-gtk3
appmenu-qt apport apport-gtk apport-symptoms aptdaemon aptdaemon-data apturl
apturl-common aspell aspell-en at-spi2-core avahi-autoipd avahi-daemon
avahi-utils bamfdaemon baobab bc binutils bluez bluez-alsa bluez-cups
bluez-gstreamer branding-ubuntu brasero brasero-cdrkit brasero-common brltty
checkbox checkbox-qt colord compiz compiz-core compiz-gnome
compiz-plugins-default consolekit cpp cpp-4.7 cracklib-runtime
cryptsetup-bin cups cups-bsd cups-client cups-common cups-filters cups-ppdc
dbus-x11 dc dconf-gsettings-backend dconf-service dconf-tools deja-dup
desktop-file-utils dictionaries-common diffstat dmz-cursor-theme
dnsmasq-base doc-base duplicity dvd+rw-tools empathy empathy-common enchant
eog espeak-data evince evince-common evolution-data-server
evolution-data-server-common example-content file-roller firefox
firefox-globalmenu firefox-gnome-support folks-common fontconfig
fontconfig-config fonts-freefont-ttf fonts-kacst fonts-kacst-one
fonts-khmeros-core fonts-lao fonts-liberation fonts-lklug-sinhala
fonts-nanum fonts-opensymbol fonts-sil-abyssinica fonts-sil-padauk
fonts-takao-pgothic fonts-thai-tlwg fonts-tibetan-machine fonts-tlwg-garuda
fonts-tlwg-kinnari fonts-tlwg-loma fonts-tlwg-mono fonts-tlwg-norasi
fonts-tlwg-purisa fonts-tlwg-sawasdee fonts-tlwg-typewriter
fonts-tlwg-typist fonts-tlwg-typo fonts-tlwg-umpush fonts-tlwg-waree
foomatic-db-compressed-ppds foomatic-db-engine foomatic-filters freerdp-x11
gcalctool gcc gcc-4.7 gconf-service gconf-service-backend gconf2
gconf2-common gcr gdb gedit gedit-common genisoimage geoclue
geoclue-ubuntu-geoip gettext ghostscript ghostscript-cups ghostscript-x
gir1.2-accounts-1.0 gir1.2-appindicator3-0.1 gir1.2-atk-1.0 gir1.2-atspi-2.0
gir1.2-dbusmenu-glib-0.4 gir1.2-dee-1.0 gir1.2-freedesktop gir1.2-gdata-0.0
gir1.2-gdkpixbuf-2.0 gir1.2-gmenu-3.0 gir1.2-gnomebluetooth-1.0
gir1.2-gnomekeyring-1.0 gir1.2-goa-1.0 gir1.2-gst-plugins-base-0.10
gir1.2-gstreamer-0.10 gir1.2-gtk-3.0 gir1.2-gtksource-3.0 gir1.2-gudev-1.0
gir1.2-indicate-0.7 gir1.2-javascriptcoregtk-3.0 gir1.2-messagingmenu-1.0
gir1.2-notify-0.7 gir1.2-pango-1.0 gir1.2-peas-1.0 gir1.2-rb-3.0
gir1.2-signon-1.0 gir1.2-soup-2.4 gir1.2-syncmenu-0.1 gir1.2-totem-1.0
gir1.2-totem-plparser-1.0 gir1.2-ubuntuoneui-3.0 gir1.2-unity-5.0
gir1.2-vte-2.90 gir1.2-webkit-3.0 gir1.2-wnck-3.0 gksu glib-networking
glib-networking-common glib-networking-services gnome-accessibility-themes
gnome-bluetooth gnome-contacts gnome-control-center
gnome-control-center-data gnome-control-center-signon gnome-desktop3-data
gnome-disk-utility gnome-font-viewer gnome-games-data gnome-icon-theme
gnome-icon-theme-symbolic gnome-keyring gnome-mahjongg gnome-media
gnome-menus gnome-online-accounts gnome-orca gnome-power-manager
gnome-screensaver gnome-screenshot gnome-session gnome-session-bin
gnome-session-canberra gnome-session-common gnome-settings-daemon
gnome-sudoku gnome-system-log gnome-system-monitor gnome-terminal
gnome-terminal-data gnome-user-guide gnome-user-share gnomine growisofs
gsettings-desktop-schemas gsfonts gstreamer0.10-alsa gstreamer0.10-gconf
gstreamer0.10-nice gstreamer0.10-plugins-base
gstreamer0.10-plugins-base-apps gstreamer0.10-plugins-good
gstreamer0.10-pulseaudio gstreamer0.10-tools gstreamer0.10-x gtk2-engines
gtk2-engines-murrine gtk3-engines-unico gucharmap guile-1.8-libs gvfs
gvfs-backends gvfs-bin gvfs-common gvfs-daemons gvfs-fuse gvfs-libs gwibber
gwibber-service gwibber-service-facebook gwibber-service-identica
gwibber-service-twitter hardening-includes hicolor-icon-theme hpijs hplip
hplip-data humanity-icon-theme hunspell-en-us hwdata ibus ibus-gtk ibus-gtk3
ibus-pinyin ibus-pinyin-db-android ibus-pinyin-db-open-phrase ibus-table
im-switch indicator-applet indicator-application indicator-appmenu
indicator-datetime indicator-messages indicator-power indicator-printers
indicator-session indicator-sound inputattach intel-gpu-tools
intltool-debian iputils-arping kerneloops-daemon landscape-client-ui-install
language-selector-gnome libaa1 libaccount-plugin-1.0-0 libaccounts-glib0
libaccounts-qt1 libappindicator1 libappindicator3-1 libapt-pkg-perl
libarchive-zip-perl libarchive12 libart-2.0-2 libasound2 libasound2-plugins
libaspell15 libasyncns0 libatasmart4 libatk-adaptor libatk-adaptor-data
libatk-bridge2.0-0 libatk1.0-0 libatk1.0-data libatkmm-1.6-1 libatspi2.0-0
libaudio2 libavahi-client3 libavahi-common-data libavahi-common3
libavahi-core7 libavahi-glib1 libavahi-gobject0 libavc1394-0 libbamf3-0
libbluetooth3 libboost-date-time1.49.0 libbrasero-media3-1 libbrlapi0.5
libburn4 libc-dev-bin libc6-dev libcaca0 libcairo-gobject2 libcairo-perl
libcairo2 libcairomm-1.0-1 libcamel-1.2-40 libcanberra-gtk-module
libcanberra-gtk0 libcanberra-gtk3-0 libcanberra-gtk3-module
libcanberra-pulse libcanberra0 libcap2 libcap2-bin libcdio-cdda1
libcdio-paranoia1 libcdio13 libcdparanoia0 libck-connector0 libclone-perl
libclutter-1.0-0 libclutter-1.0-common libclutter-gst-1.0-0
libclutter-gtk-1.0-0 libcmis-0.2-2 libcogl-common libcogl-pango0 libcogl9
libcolord1 libcompizconfig0 libcrack2 libcroco3 libcrypt-passwdmd5-perl
libcryptsetup4 libcups2 libcupscgi1 libcupsfilters1 libcupsimage2
libcupsmime1 libcupsppdc1 libcurl3 libcurl3-nss libdaemon0 libdatrie1
libdbusmenu-glib4 libdbusmenu-gtk3-4 libdbusmenu-gtk4 libdbusmenu-qt2
libdconf1 libdecoration0 libdee-1.0-4 libdevmapper-event1.02.1
libdigest-hmac-perl libdiscid0 libdjvulibre-text libdjvulibre21
libdmapsharing-3.0-2 libdotconf1.0 libdpkg-perl libdrm-nouveau2 libdv4
libebackend-1.2-5 libebook-1.2-14 libecal-1.2-15 libedata-book-1.2-15
libedata-cal-1.2-18 libedataserver-1.2-17 libemail-valid-perl libenchant1c2a
libespeak1 libevdocument3-4 libevview3-3 libexempi3 libexif12 libexiv2-12
libexttextcat-1.0-0 libexttextcat-data libfarstream-0.1-0
libfile-basedir-perl libfile-copy-recursive-perl libfile-desktopentry-perl
libfile-fcntllock-perl libfile-mimeinfo-perl libflac8 libfolks-eds25
libfolks-telepathy25 libfolks25 libfontconfig1 libfontembed1 libfontenc1
libframe6 libfreerdp-plugins-standard libfreerdp1 libfs6 libgail-3-0
libgail-common libgail18 libgck-1-0 libgconf-2-4 libgcr-3-1 libgcr-3-common
libgd2-xpm libgdata-common libgdata13 libgdk-pixbuf2.0-0
libgdk-pixbuf2.0-common libgee2 libgeis1 libgeoclue0 libgettextpo0
libgexiv2-1 libgksu2-0 libgl1-mesa-dri libgl1-mesa-glx libglapi-mesa
libglew1.8 libglewmx1.8 libglib-perl libglib2.0-0 libglib2.0-bin
libglib2.0-data libglibmm-2.4-1c2a libglu1-mesa libgmime-2.6-0 libgmp10
libgnome-bluetooth11 libgnome-control-center1 libgnome-desktop-3-4
libgnome-keyring-common libgnome-keyring0 libgnome-media-profiles-3.0-0
libgnome-menu-3-0 libgnome-menu2 libgnomekbd-common libgnomekbd8
libgoa-1.0-0 libgoa-1.0-common libgomp1 libgpgme11 libgphoto2-2
libgphoto2-l10n libgphoto2-port0 libgpod-common libgpod4 libgrail5 libgrip0
libgs9 libgs9-common libgssdp-1.0-3 libgstreamer-plugins-base0.10-0
libgstreamer0.10-0 libgtk-3-0 libgtk-3-bin libgtk-3-common libgtk2-perl
libgtk2.0-0 libgtk2.0-bin libgtk2.0-common libgtkmm-3.0-1
libgtksourceview-3.0-0 libgtksourceview-3.0-common libgtkspell-3-0
libgtop2-7 libgtop2-common libgucharmap-2-90-7 libgudev-1.0-0 libgupnp-1.0-4
libgupnp-igd-1.0-4 libgusb2 libgutenprint2 libgweather-3-1
libgweather-common libgwibber-gtk3 libgwibber3 libgxps2 libhpmud0
libhunspell-1.3-0 libhyphen0 libibus-1.0-0 libical0 libice6 libicu48
libido3-0.1-0 libiec61883-0 libieee1284-3 libijs-0.35 libimobiledevice3
libindicate5 libindicator3-7 libindicator7 libio-pty-perl
libio-socket-inet6-perl libipc-run-perl libisofs6 libitm1 libiw30
libjack-jackd2-0 libjasper1 libjavascriptcoregtk-3.0-0 libjbig0 libjbig2dec0
libjpeg-turbo8 libjpeg8 libjs-jquery libjson-glib-1.0-0 libjson0 libjte1
libkpathsea6 liblcms1 liblcms2-2 liblightdm-gobject-1-0 liblircclient0
libllvm3.1 liblouis-data liblouis2 libltdl7 liblua5.1-0 liblvm2app2.2
libmailtools-perl libmeanwhile1 libmessaging-menu0 libmetacity-private0a
libmhash2 libminiupnpc8 libmission-control-plugins0 libmng1 libmpc2 libmpfr4
libmtdev1 libmtp-common libmtp-runtime libmtp9 libmusicbrainz5-0 libmx-1.0-2
libmx-bin libmx-common libmysqlclient18 libmythes-1.2-0 libnatpmp1
libnautilus-extension1a libneon27-gnutls libnet-dns-perl
libnet-domain-tld-perl libnet-ip-perl libnetfilter-conntrack3 libnettle4
libnice10 libnl-route-3-200 libnm-glib-vpn1 libnm-glib4 libnm-gtk-common
libnm-gtk0 libnm-util2 libnotify-bin libnotify4 libnspr4 libnss-mdns libnss3
libnux-3.0-0 libnux-3.0-common liboauth0 libogg0 libopencc1 libopenobex1
liborc-0.4-0 libpackagekit-glib2-14 libpam-cap libpam-ck-connector
libpam-freerdp libpam-gnome-keyring libpam-xdg-support libpanel-applet-4-0
libpango-perl libpango1.0-0 libpangomm-1.4-1 libpaper-utils libpaper1
libpcsclite1 libpeas-1.0-0 libpeas-common libperl5.14 libpixman-1-0
libplist1 libpolkit-agent-1-0 libpolkit-backend-1-0 libpoppler-glib8
libpoppler28 libportaudio2 libprotobuf7 libprotoc7 libproxy1
libproxy1-plugin-gsettings libproxy1-plugin-networkmanager libpth20
libpulse-mainloop-glib0 libpulse0 libpulsedsp libpurple-bin libpurple0
libpwquality1 libpython3.2 libqjson0 libqpdf8 libqt4-dbus libqt4-declarative
libqt4-designer libqt4-help libqt4-network libqt4-script libqt4-scripttools
libqt4-sql libqt4-sql-mysql libqt4-sql-sqlite libqt4-svg libqt4-test
libqt4-xml libqt4-xmlpatterns libqtassistantclient4 libqtcore4 libqtgui4
libqtwebkit4 libquadmath0 libquvi-scripts libquvi7 libraptor2-0 librasqal3
libraw1394-11 libraw5 librdf0 libreoffice-base-core libreoffice-calc
libreoffice-common libreoffice-core libreoffice-draw libreoffice-emailmerge
libreoffice-gnome libreoffice-gtk libreoffice-help-en-us libreoffice-impress
libreoffice-math libreoffice-ogltrans libreoffice-pdfimport
libreoffice-presentation-minimizer libreoffice-presenter-console
libreoffice-style-human libreoffice-style-tango libreoffice-writer
librest-0.7-0 librhythmbox-core6 librsvg2-2 librsvg2-common librsync1
libsamplerate0 libsane libsane-common libsane-hpaio libsecret-1-0
libsecret-common libsensors4 libsgutils2-2 libshout3 libsignon-extension1
libsignon-glib1 libsignon-plugins-common1 libsignon-qt1 libsm6 libsmbclient
libsndfile1 libsnmp-base libsnmp15 libsocket6-perl libsonic0
libsoup-gnome2.4-1 libsoup2.4-1 libspectre1 libspeechd2 libspeex1
libspeexdsp1 libssh-4 libstartup-notification0 libsync-menu1
libsyncdaemon-1.0-1 libsysfs2 libt1-5 libtag1-vanilla libtag1c2a libtalloc2
libtdb1 libtelepathy-farstream2 libtelepathy-glib0 libtelepathy-logger2
libthai-data libthai0 libtheora0 libtiff5 libtimezonemap1
libtotem-plparser17 libtotem0 libtxc-dxtn-s2tc0 libubuntuoneui-3.0-1
libudisks2-0 libufe-xidgetter0 libunistring0 libunity-core-6.0-5
libunity-misc4 libunity-protocol-private0 libunity-webapps0 libunity9
libupower-glib1 liburi-perl libusbmuxd2 libutempter0 libuuid-perl libv4l-0
libv4lconvert0 libvisual-0.4-0 libvisual-0.4-plugins libvncserver0
libvorbis0a libvorbisenc2 libvorbisfile3 libvte-2.90-9 libvte-2.90-common
libwacom-common libwacom2 libwavpack1 libwbclient0 libwebkitgtk-3.0-0
libwebkitgtk-3.0-common libwhoopsie0 libwmf0.2-7 libwmf0.2-7-gtk libwnck-3-0
libwnck-3-common libwnck-common libwnck22 libwpd-0.9-9 libwpg-0.2-2
libwps-0.2-2 libx11-xcb1 libx86-1 libxatracker1 libxaw7 libxcb-dri2-0
libxcb-glx0 libxcb-render0 libxcb-shape0 libxcb-shm0 libxcb-util0
libxcomposite1 libxcursor1 libxdamage1 libxfixes3 libxfont1 libxft2 libxi6
libxinerama1 libxkbfile1 libxklavier16 libxml2 libxmu6 libxp6 libxpm4
libxrandr2 libxrender1 libxres1 libxslt1.1 libxt6 libxtst6 libxv1 libxvmc1
libxxf86dga1 libxxf86vm1 libyajl2 libyaml-tiny-perl libyelp0
libzeitgeist-1.0-1 libzephyr4 light-themes lightdm
lightdm-remote-session-freerdp lightdm-remote-session-uccsconfigure lintian
linux-libc-dev linux-sound-base make manpages-dev mcp-account-manager-uoa
media-player-info metacity-common mobile-broadband-provider-info
modemmanager mousetweaks mscompress mtools mysql-common nautilus
nautilus-data nautilus-sendto nautilus-sendto-empathy nautilus-share
network-manager network-manager-gnome network-manager-pptp
network-manager-pptp-gnome notification-daemon notify-osd notify-osd-icons
nux-tools obex-data-server obexd-client onboard oneconf openprinting-ppds
overlay-scrollbar overlay-scrollbar-gtk2 overlay-scrollbar-gtk3 patch
patchutils pcmciautils perl perl-base perl-modules pinyin-database
pkg-config plymouth-label plymouth-theme-ubuntu-logo pm-utils policykit-1
policykit-1-gnome policykit-desktop-privileges poppler-data poppler-utils
pptp-linux printer-driver-c2esp printer-driver-foo2zjs
printer-driver-gutenprint printer-driver-hpcups printer-driver-hpijs
printer-driver-min12xxw printer-driver-pnm2ppa printer-driver-postscript-hp
printer-driver-ptouch printer-driver-pxljr printer-driver-sag-gdi
printer-driver-splix protobuf-compiler pulseaudio
pulseaudio-module-bluetooth pulseaudio-module-gconf pulseaudio-module-x11
pulseaudio-utils python-appindicator python-apport python-aptdaemon
python-aptdaemon.gtk3widgets python-cairo python-configglue python-cups
python-cupshelpers python-dbus python-dbus-dev python-debtagshw python-defer
python-dirspec python-gconf python-gi python-gi-cairo python-gnomekeyring
python-gnupginterface python-gobject python-gobject-2 python-gst0.10
python-gtk2 python-httplib2 python-ibus python-imaging python-libxml2
python-lxml python-mako python-markupsafe python-notify python-oauth
python-openssl python-pam python-pexpect python-piston-mini-client
python-pkg-resources python-problem-report python-protobuf python-pycurl
python-pyinotify python-qt4 python-qt4-dbus python-renderpm python-reportlab
python-reportlab-accel python-serial python-simplejson python-sip
python-smbc python-twisted-bin python-twisted-core python-twisted-names
python-twisted-web python-ubuntu-sso-client python-ubuntuone-client
python-ubuntuone-control-panel python-ubuntuone-storageprotocol python-uno
python-xdg python-zeitgeist python-zope.interface python3-apport
python3-aptdaemon python3-aptdaemon.gtk3widgets python3-aptdaemon.pkcompat
python3-brlapi python3-cairo python3-crypto python3-defer
python3-distupgrade python3-gi-cairo python3-httplib2 python3-louis
python3-lxml python3-oauthlib python3-pkg-resources python3-problem-report
python3-pyatspi2 python3-pycurl python3-software-properties python3-speechd
python3-update-manager python3-virtkey python3-xdg python3-xkit python3.2
python3.2-minimal qdbus qpdf qt-at-spi radeontool remmina remmina-common
remmina-plugin-rdp remmina-plugin-vnc remote-login-service rfkill rhythmbox
rhythmbox-data rhythmbox-mozilla rhythmbox-plugin-cdrecorder
rhythmbox-plugin-magnatune rhythmbox-plugin-zeitgeist rhythmbox-plugins
rhythmbox-ubuntuone rtkit samba-common samba-common-bin sane-utils seahorse
session-migration sessioninstaller sgml-base shared-mime-info shotwell
signon-keyring-extension signon-plugin-oauth2 signon-plugin-password
signon-ui signond simple-scan smbclient sni-qt software-center
software-center-aptdaemon-plugins software-properties-common
software-properties-gtk sound-theme-freedesktop speech-dispatcher
ssh-askpass-gnome ssl-cert syslinux syslinux-common syslinux-legacy
system-config-printer-common system-config-printer-gnome
system-config-printer-udev telepathy-gabble telepathy-haze telepathy-idle
telepathy-indicator telepathy-logger telepathy-mission-control-5
telepathy-salut thin-client-config-agent thunderbird thunderbird-globalmenu
thunderbird-gnome-support toshset totem totem-common totem-mozilla
totem-plugins transmission-common transmission-gtk ttf-dejavu-core
ttf-indic-fonts-core ttf-punjabi-fonts ttf-ubuntu-font-family
ttf-wqy-microhei ubuntu-artwork ubuntu-docs ubuntu-drivers-common
ubuntu-extras-keyring ubuntu-mono ubuntu-release-upgrader-core
ubuntu-release-upgrader-gtk ubuntu-settings ubuntu-sounds ubuntu-sso-client
ubuntu-sso-client-qt ubuntu-system-service ubuntu-wallpapers
ubuntu-wallpapers-quantal ubuntuone-client ubuntuone-client-gnome
ubuntuone-control-panel ubuntuone-control-panel-qt ubuntuone-couch udisks
udisks2 unattended-upgrades unity unity-asset-pool unity-common
unity-greeter unity-lens-applications unity-lens-files unity-lens-gwibber
unity-lens-music unity-lens-photos unity-lens-shopping unity-lens-video
unity-scope-gdocs unity-scope-musicstores unity-scope-video-remote
unity-services unity-webapps-common unity-webapps-service uno-libs3 unzip
update-inetd update-manager update-manager-core update-notifier
update-notifier-common upower ure usb-creator-common usb-creator-gtk
usb-modeswitch usb-modeswitch-data usbmuxd vbetool vino wamerican whoopsie
wireless-tools wodim wpasupplicant x11-apps x11-common x11-session-utils
x11-utils x11-xfs-utils x11-xkb-utils x11-xserver-utils xbitmaps
xcursor-themes xdg-user-dirs xdg-user-dirs-gtk xdg-utils xdiagnose
xfonts-base xfonts-encodings xfonts-mathml xfonts-scalable xfonts-utils
xinit xinput xml-core xorg xorg-docs-core xserver-common xserver-xorg
xserver-xorg-core xserver-xorg-input-all xserver-xorg-input-evdev
xserver-xorg-input-mouse xserver-xorg-input-synaptics
xserver-xorg-input-vmmouse xserver-xorg-input-wacom xserver-xorg-video-all
xserver-xorg-video-ati xserver-xorg-video-cirrus xserver-xorg-video-fbdev
xserver-xorg-video-intel xserver-xorg-video-mach64 xserver-xorg-video-mga
xserver-xorg-video-modesetting xserver-xorg-video-neomagic
xserver-xorg-video-nouveau xserver-xorg-video-openchrome
xserver-xorg-video-qxl xserver-xorg-video-r128 xserver-xorg-video-radeon
xserver-xorg-video-s3 xserver-xorg-video-savage
xserver-xorg-video-siliconmotion xserver-xorg-video-sis
xserver-xorg-video-sisusb xserver-xorg-video-tdfx xserver-xorg-video-trident
xserver-xorg-video-vesa xserver-xorg-video-vmware xterm xul-ext-ubufox
xul-ext-unity xul-ext-websites-integration yelp yelp-xsl zeitgeist
zeitgeist-core zeitgeist-datahub zenity zenity-common zip
Você pode copiar e colar isso em uma linha de comando do apt-get remove.