Мне init 3 не помог, т.к. у дебиан и Ubuntu изначально другая система инициализации (BSD, а не system-V).
rc-update может уже не работать, т.к. теперь в Ubuntu используется upstart.
Хотя идеологически это ИМХО самый верный способ, поэтому нужно курить настройки сервисов.
Кроме gdm графику могут запускать kdm (если стоит kde) и xdm (вроде именно его тянет xubuntu, хотя точно не помню)
Для начала попробуйте перейти в консоли по Alt+Ctrl+F1 и остановить графику так (если правильно помню)
service gdm stop
Если после этого графика отрубится, значит имя сервиса угадали правильно. А как убрать его из автозагрузки, не знаю, поэтому
man service
или
man upstart