Possible fixes include, but are not limited to:
- Make sure your Windows system time is correct.
- Reregister softpub.dll using the command regsvr32.exe:
In Windows: Start > Run > regsvr32 softpub.dll
- Remove any Internet Explorer proxy server settings:
In Internet Explorer: Tools > Internet Options > Connections > LAN Settings... > Untick "Use a proxy server for your LAN"
(note: close Messenger completely before doing anything)