What you could do, is in MSN Messenger 7.5, go to Contacts > Save Instant Messaging Contacts. Save the file somewhere. Then install Windows Live Messenger, go to Contacts > Import Instant Messaging Contacts, select the file you saved before. This file has all your contacts saved to it, so they should all be added. Hopefully that will work, your cotnacts might have to accept an invite if they get one.
You should contact
Windows Live Messenger Feedback if you havn't done so already. Tell them your problem.