Interesting...

Heh, I'm buggered. Without looking at the machine, it's difficult to troubleshoot.

If you use the GPO management tool (the new one for Win2k3), it makes it easier to determine the permissions in effect on a certain policy as well as exactly who they apply to. Are you able to find out what the two denials are set for and at what level they apply? Determining how to do this would be the first thing that I did.

Of course, I'm assuming that you've logged on with a domain admin logon and that you're the only domain admin. It isn't possible that someone made a change without your knowledge, is it?