Thanks for the links. I'll give the WMI fix a try. Besides reboots we've also been able to temporarily fix the problem (and I stress temporarily) by following the instructions in this link.
http://blogs.msdn.com/echarran/archive/2006/01/03/509061.aspx