getting a similar problem here, will try the remove from / add to domain trick at some point.
IMHO a layered approach to security is essential and relying on only a perimeter firewall is no longer adequate any member of staff could bring in a virus/worm on a pendrive or an infected laptop and your perimeter security is rendered useless. It takes no time at all to use GP to open all of the necessary ports.
Just my opinion.
@ adamf, i've known this happen a number of times in fact i had one this morning, no amount of policy refreshes or reboots would sort it but rejoining the domain did.
You can use Psexec a sysinternal tool to update group policy to remote machine ,you can apply to all computers in a domain controller in a single command you can download Psexec the syntax is follows
Psexec \\* gpupdate /force
\\* means all computers you can change it as computer name for single machine
after you can check the event viewer whether policy is updated or not
You can found more information from here PsExec