Проблема оказалась не столько в Убунте, сколько в программе TightVNC viewer. Из-под дефолтной виндовой программы заходит без проблем. А TightVNC viewer пишет, что нет отклика от сервера.
Но если запустить настройку Удаленного рабочего стола, то сразу начинает работать. Мистика.