1. Go to MSN.com
2. Click 'Sign In' in the upper right hand corner
3. Sign In using the credentials you use for your Messenger account
4. You will be taken to a screen that asks for a new password
5. Follow the instructions on the screen to enter a new password
6. After you are done, try and log into your Messenger software again with the new password
