I couldn't figure out how to get the "New application rule" mentioned in the FAQ to work, but FWIW I found doing this did fix the problem for me:
Go to Settings -> Components -> Firewall customize -> Policies -> Packet rules... -> Add a new row and enter the following:
Enabled: checked
Name: Remote desktop out
Action: Allow
Protocol: TCP (6)
Direction: Out
Address: <leave blank>
Local Port: <leave blank>
Remote Port: 3389
ICMP Type: <leave blank>
Profile: All