When I try to log into Windows Live Messenger, I get the following error;

"Signing into Windows Live Messenger failed because the service is temporarily unavailable. Please try again Later"

"Error code: 80040200"

It has been like that for a couple of weeks now. I've tried everything I could find on the internet about this, but no solution has worked so far.

I've, un-installed, reinstalled, deleted cache, registry entries, tried killing the wlcomm process, etc (solutions from web), but none have worked.

I've got Avira AntiVir premium, and have scanned with MBAM. All clean.

It is a new PC, and it did work originally, then just stopped working one day.

Any Ideas?

EDIT: It is 64-bit by the way in case it makes a difference

See If this could Help:

Beginning with 2009, Messenger makes use of a Windows Live
Contacts framework/executable which handles everything related to contacts against all the Windows Live products. However as a starting point, it is installed or you would see a
different error to this.

Press the Windows key and then R to bring up the Run box, and put in the following:
%userprofile%\local settings\application data\microsoft\windows live contacts
then click OK

Are there folders listed here? Right-click somewhere in the explorer window (not one of the
folders) and choose Properties. Has there been any files created here (they'll be hidden by
default, but they'll show up in the properties)?

Finally, delete all the folders here (it's just a cache) and then attempt to sign in again.

Thanks, I tried this but still no good. It just gives e a "contacts not available" error instead then when I press retry it reverts to the previous error.