Você já verificou como o seu firewall está lidando com as solicitações recebidas?
O que eu acho é que você está tentando usar um sistema como vnc ou krdc para obter acesso à sua área de trabalho.
Se você não estiver usando um software de firewall, dê uma chance ao "Firestarter", que é facilmente instalado ao soltar
sudo apt-get install firestarter
Ou via Synaptic. Depois de parar o firewall, verifique o que acontece quando você tenta obter a conexão. Se isso parece resolver seu problema, você deve definir uma exceção para essa tarefa.