Are you changing these from your own machine? (if so, I strongly urge you NOT do this, as it's likely your machine has been compromised, which will be how they obtained the login credentials to begin with).
Contact your hosting company, inform them your site has been compromised, and ask them to change the passwords for you. Make sure you use a KNOWN CLEAN computer, to check e-mail (assuming they send the new passwords via e-mail), and get your own machine checked;
http://www.malwarebytes.org/forums/index.php?showtopic=9573/edit
As an addendum, as per the advice I linked you to, I also strongly urge you delete ALL files and folders from your site, and upload a KNOWN CLEAN backup. This will save you the hours it will take to go through each file and folder manually (and nope, this cannot be skipped or "short cutted")