I suggest everyone's password be randomized.
There is a danger in that, because several people (especially users with old accounts) will not have updated their email address and will therefore not receive their new password. Despite that, I strongly support this suggestion, dealing with people who have lost access is going to result in a lot less pain than having malicious kiddies logging onto overlooked accounts for months to come.
Also, I think virtualsue is absolutely right, take the site down now and don't put it back up until it's running on a known-clean machine.