It should be as easy as telling apt you want to remove Xorg and it will trigger removal of all the packages which depend on X.

sudo apt-get remove xserver-xorg-core

Just in case that doesn't work, here is a list of everything which ubuntu-desktop triggers to be installed on my bare ubuntu-server install:

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

You could copy and paste that into an apt-get remove command line.