Só para verificar, você está usando a porta TCP 3389 (padrão de RDP), certo? Em qual escopo você tem a regra de firewall? Se você definiu a regra FW para um escopo diferente do que o sistema operacional acha que está vindo, ela não corresponderá a ela. ou seja, se o adaptador de rede estiver em um escopo "público" e a regra que você inserir for para um escopo de "domínio", ele não corresponderá.
EDIT: Doh. Só percebi que eu interpretei mal isso - eu pensei que você disse desktop remoto. Você tem o 1433 e o 1434 UDP abertos?