If the firewall is correct them the issue must be with the router, presuming there are no 3rd party software firewalls or security suits on the PC which could cause the same issue as the windows firewall.
If you are/were using remote.domainname.com:3391 and you haven't changed the listening port on the PC then the firewall/router needs to have a forwarding rule that forwards external pointed to port 3391 to an internal IP (that of the PC to which you want to connect) on port 3389. Can you verify that?
