Demorou um pouco, mas descobri que precisava adicionar uma linha às regras do meu firewall para abrir a porta: 3389.
Veja como:
Em um tipo de terminal: sudo nano /etc/iptables.firewall.rules
Adicione a seguinte linha: -A INPUT -p tcp --dport 3389 -j ACCEPT
Salvar usando CTRL-W