If the e-mail address on your account was changed, how did you recieve the alert(e-mail?)? A common phishing scam is to send these "alerts" so you will log in via the phishing site to check the account,hence handing over the password to them. Not saying thats what happened, but you may want to go back to e-bay(the REAL e-bay)and change it again.
-Maestr0
