Работаю по такой же схеме. Поставить hamachi на оба компа, на Винду поставить Radmin сервер, на Ubuntu Radmin Viewer Portable запущенный через wine. Все прекрасно работает. Для Ubuntu есть gui для hamachi, называется haguichi. Google в помощь. Или вариант с teamviewer, предложенный выше. Обе связки пробивают любой nat.