I just tried installing the skin from here
http://www.rolandunderg.net/skins.php?act=download&&id=pmsn and it worked fine.
Are you sure you are installing the skin on a clean version. This is the only thing I can think of.
-Go to control panel, then add/remove programs, then go to MSN Messenger and click remove.
-Then reboot your computer
-Next, Remove the MSN Messenger folder in Program Files and in C:\Documents and Settings\<username>\Application Data\Microsoft\MSN Messenger. ( Note: this will remove all custom emoticons etc. To backup these files you can use
CE/DP Backup Wizard
Then download MSN from
http://messenger.msn.com and install it.
Then try installing the skin.