It sounds like the users have been deleted from the database. But, I probably couldn't help with why. I just know that's exactly what happens when you delete a user. Can you find the users in your AdminCP? Do you have other admins? Is it possible that somebody deleted them on purpose? Have you checked your admin log? Have you been having database problems?
That doesn't sound good, I hope somebody else has a better answer