Ubuntu trae por defecto un cliente VNC, pero esta no es la tecnología predominante en Windows.
Necesitaba un cliente para RDP.
Después de buscar en google, conseguí la solución: Remmina
Para instalarla en Ubuntu, sólo hace falta ejecutar
$ sudo aptitude install remminaUna vez instalado, se abre la aplicación, se introducen los datos del servidor, y listo.