This one had me stumped, but it’ll teach me to search the internet properly before blundering through. Even if you allow the Windows Firewall to accept Remote Desktop Connections you still need to enable Terminal Services elsewhere in the GP hierarchy. D’oh!
Here’s what you need to enable Remote Desktop remotely:
Computer Configuration > Administrative Templates > Network > Network Connections > Windows Firewall > Domain Profile > Windows Firewall: Allow Remote Desktop Exception
Computer Configuration > Administrative Templates > Windows Components > Terminal Services > Allow users to connect remotely using Terminal Services
Enable both of those options and you’ll be Remote Desktop-ing into PCs by the next day 🙂 (or rather, until your Domain clients refresh their Group Policy settings ;))