Windows Firewall denies terminal server connections?

Running Windows Firewall on our 2003 server domain controller seems to block access to our terminal servers. I have opened what i think are all related ports for TS and Remote Desktop and RPC, specifically 3389, but everyone still gets a Access is Denied error when attempting to connect.
Any suggestions? And i can provide more info obviously if that helps.