Step 1 - Go to https://omega.contacts.msn.com
Step 2 - If your browser makes a fuss about this (Firefox will) then add an exception when prompted and you'll be greeted with a Directory Denied error. Don't worry this is normal.
Step 3 - Click on the Favicon or the Padlock if it's showing and view the certificate
Step 4 - Confirm that the issue date is 15th of November 2010

Step 5 - Under the Details tab, export the certificate to a file and save it.
Step 6 - Rename the exported file "omega.contacts.msn.com" and replace your old certificate with it. You'll find the certificate in one of the following directories:
Windows - %userprofile%\AppData\Roaming\.purple\certificates\x509\tls_peers\
Linux - /home/username/.purple/certificates/x509/tls_peers
At the moment in time I'm unaware of a Mac OS X fix or even that Adium is affected. I'll edit this post once I know more
Update 20/11/2010 - As of the time of writing aMSN and Empathy are unaffected so any Linux users having troubles getting the certificate to take have another option.