Im wondering if some permissions were stuffed somehow after the Windows updates.

You need to narrow down the cause for the Access Is Denied WMI event. You can turn on a WMI trace in Windows event viewer, instructions here http://msdn.microsoft.com/en-us/library/windows/desktop/aa826686%28v=vs.85%29.aspx

Then try changing the service account again, there should be an event in the log, look for any errors.