Which provided the following solution:
certutil -setreg ca\setupstatus +512
net stop certsvc
net start certsvc
And now Microsoft issued KB967332 5 months after that post.
Published on Saturday, February 14, 2009 in Microsoft
Just a very interesting series of posts by Jorge on how the Active Directory clients determine which domain controller servers their logon request and which domain controller sends the GPO files over.
DC Locator process part 1
DC Locator process part 2
DC Locator process part 3
A small add-on: using start - run - cmd and execute "set" you can easily determine your logon server. Determining which DC sent the GPO's can be determined by running "gpresult /R" (Windows 2008) or "gpresult" (Vista)
The following Technet article is also a nice source of information: How DNS Support for Active Directory Works
[Update:] added NTP as said by Brent in the comments
The following post will explain how to let basic Active Directory related network traffic such as logon requests or replication traffic, be it either sysvol items or AD objects, happen through firewalls. This doesn't mean I'm totally in favour of implementing a firewall between every possible environment. But you might encounter projects where firewalls are used between different sites or just internally between clients and servers. In that case you might find the following interesting:
The following list is an overview of the AD related services with their required ports: