change the password - as you've done, and also change the security / password recovery questions.
if you still have problems after that its because the other user is still permanently logged on - in which case you'd have to get microsoft to close all open links to the account and then restart it with yet another new password
From memory theres an option to do this online through the lost password recovery process - I think one of the options is "someone else is accessing my account" or words like that. Using that one should bump them