You also need to run a malware check on the site itself, or ask your host to do so for you. (Unless it's a very small site, in which case it might be just as easy to delete everything and upload clean copies from your local PC.) Check your .htaccess file, too, for unauthorised changes.
And yes, I would change all passwords associated with the site. If somebody has gained access, you have no way of knowing where they've been or what information they've gained, so your safest bet is to change all passwords and ensure you use only strong passwords in future.