Greetings

The "80072efd error" simply means it can't connect to the service.  There's nothing to fix
per se as it's just a general connectivity error.

Here are some suggestions you should check/try if you haven't already.

1.  The date on your computer needs to be set properly -- double click the clock in the
notification area and verify that the time and date are set correctly.
3.  If you use a firewall (like ZoneAlarm, Norton Internet Security etc. ), it's possible
that Messenger doesn't have the correct rights to access the Internet, especially since you
upgraded.  You may need to re/add Messenger to the allowed list of programs in your firewall
if this is the case.
3.  If you disabled your firewall in the past, it still may be blocking Messenger -- try
restarting it and see if that helps the situation.  You also might try uninstalling an
installed firewall, to verify that it isn't causing a problem (even if it is disabled).
4.  Click Start, then Run, and enter the following:
regsvr32 softpub.dll
then click OK
and do the same for the following:
regsvr32 wintrust.dll
regsvr32 initpki.dll
regsvr32 MSXML3.dll

Finally, if that doesn't work, you can actually downgrade to the updated 7.0 version.  To do
so, download from here:
http://microsoft.com/downloads/details.aspx?FamilyID=cf49c56c-8b3e-4eae-9904-950
5f47bed45

Then you'll need to engage compatibility mode so it doesn't force you to upgrade.  To do so,
go to the \Program files\MSN Messenger folder, right click on the msnmsgr.exe file, choose
Properties, then the Compatibility tab, choose Windows 2000, click OK and then run Messenger
as per normal.