Saída Terminal Services

Bom dia caros amigos.
Sempre utilizei normalmente o Remote Desktop Connection (mstsc) do Windows para acessar remotamente outras máquinas através do Terminal Services. A partir de determinado momento isso tornou-se inviável. Tanto a entrada de conexões, quanto a saída.
Estou com TUDO aberto no iptables, como segue abaixo:

root@internetsrv:~# iptables -L
Chain INPUT (policy ACCEPT)
target prot opt source destination
ACCEPT all -- anywhere anywhere

Chain FORWARD (policy ACCEPT)
target prot opt source destination
ACCEPT all -- anywhere anywhere
ACCEPT all -- anywhere anywhere

Chain OUTPUT (policy ACCEPT)
target prot opt source destination
ACCEPT all -- anywhere anywhere

Detalhe que através do comando redir consigo receber e encaminhar solicitações externas ao meu servidor ts sem problemas. O que não consigo é conectar daqui de dentro pra fora.
Porém não consigo acessar um endereço remoto a partir de uma estação, somente a partir do próprio servidor, que roda o Ubuntu 10.
Tentei utilizar o UFW (Ubuntu Firewall) para liberar a 3389 em saída, mas nada também.
Se possível, gostaria de uma luz para saber o que está ocorrendo, pois senão não me restará outra alternativa a não ser fazer uma nova instalação e reconfigurar tudo de novo :(