Even if the site appears to look like a Live ID sign in page, look for the green address bar, lock icon and company name to verify it truly is. Additionally, depending in your Windows version, browser and Live ID site you're signing into, you might need to click the ‘Sign in using enhanced security’ link on the page to see these indicators.

Finally you'll arrive at the password changing page and can change your password. One minor feature that’s been added recently is an option to prompt you to change your password every 72 days. I'm not quite sure how this will work with regards to Messenger yet, but time will tell.