Have a Windows 2000 server machine, that's set to automatically
download items and notify me for installation.

It does that splendidly, and tells me updates are available for me to
install through the nice little icon in the systemtray. I click it:
somehow the icon decides to disappear as if it never was there, and
not pop up the list of updates that I appearantly need to install...

Right, so we then go to the Windows Update site... Which seems to have
undergone a revamp of somesort...

It does not scan anything but just hits me with the following info:

The site cannot continue because one or more of these Windows services
is not running.

* Automatic Updates (allows the site to find, download and install
high-priority updates for your computer)
* Background Intelligent Transfer Service (BITS) (helps updates
download more quickly and without problems if the download process is
interrupted)
* Event Log (keeps a record of updating activities to help with
troubleshooting, if needed)
To make sure these services are running:
1. Click Start, and then click Run.
2. Type services.msc and then click OK.
3. In the list of services, double-click on Automatic Updates and then
click Properties.
4. In the Startup type list, select Automatic and click Apply.
5. Verify that the Service status is started, if the Service Status is
Stopped click on the Start Button.
6. In the list of services, double-click on Background Intelligent
Transfer Service (BITS) and then click Properties.
7. In the Startup type list, select Manual and click Apply.
8. Verify that the Service status is started, If the Service Status is
Stopped click on the Start Button.
9. In the list of services, double-click on Event Log and then click
Properties.
10. In the Startup type list, select Automatic and click Apply.
11. Verify that the Service status is started, If the Service Status
is Stopped click on the Start Button.
If this does not resolve the problem you may request help from one of
the following resources.

For self-help options:

Frequently Asked Questions
Find Solutions
Windows Update Newsgroup

I know the services are running, but looking through the whole I can't
see any reason why the updates themselves should fail... I'm
considering reapplying SP4 on the machine as a last resort, and go
from there, but since this machine also has the Roll-Up package post
SP4 (version 1) installed, I'm not sure if that'll break more then
it'll fix.

Anyone have any thoughts on this? TIA for any feedback, Neko-