Если Ваша хост-система - Windows, то, начиная с версии Ubuntu 9.10, пошли какие-то странные глюки с разными vnc-вьюерами. Правда, я сталкивался только к проблемами с русской раскладкой, но и работаю всё-таки не с VirtualBox, а с удалённым доступом на физически отдельные машины. Моё, хоть и "некошерное", решение - брать Viewer из состава RealVNC Enterprise. Интересно, что формально абсолютно тот же вьюер, выложенный как бесплатный, не решает проблем.
P.S.: Проверил, зайдя удалённо на 9.10 Desktop и 9.04 Desktop, настройки именно такие, как я писал выше, и именно из-за проблемы с неправильной раскладкой под Gnome. Кстати, эта фигня творится, как минимум, с версии 7.10, то есть баг уже превращается во всеми любимую фичу
.