Windows Update Fails (Windows Server 2008 x64)

A critical security update came out a while ago, that I have been unable to install. I've spent the better part of today trying to figure this one out and I'm stumped. I've tried using the automatic update, as well as manually downloading the update from the Microsoft website.

My systems are running Windows Server 2008 Enterprise x64. This same update is failing on three independent and isolated servers (the only Windows Server 2008 servers I have access to).

Whenever the system attempts the update I get the following error:

Installer encountered an error: 0x8007000d The data is invalid.

And it creates an companion event log seen below:

- System 

  - Provider 

   [ Name]  Microsoft-Windows-WUSA 
   [ Guid]  {09608c12-c1da-4104-a6fe-b959cf57560a} 

   EventID 3 

   Version 0 

   Level 2 

   Task 0 

   Opcode 0 

   Keywords 0x8000000000000000 

  - TimeCreated 

   [ SystemTime]  2009-10-26T18:00:08.659Z 

   EventRecordID 11 

   Correlation 

  - Execution 

   [ ProcessID]  6732 
   [ ThreadID]  6592 

   Channel Setup 

   Computer server.example.com 

  - Security 

   [ UserID]  S-1-5-21-1868723478-1673120740-2095933981-27156 


- EventData 

  UpdateTitle  
  ErrorCode 2147942413 
  ErrorString The data is invalid. 
  CommandLine "C:\Windows\system32\wusa.exe" "C:\Users\admin\Desktop\Windows6.0-KB967723-x64.msu"

Does anyone have any ideas?

Call Microsoft. Provided you have a licensed product, security cases are covered by their free support and is actually quite good.