Yup, sounds like a reinstall to me. If the boot disc says there are no user accounts, then there's nothing there for you to log in with.
Although... They MIGHT have enabled root. Try logging in as 'root' with no password.
If it's asking for a username and password, rather than a list of users, then it was set to do that. That seems like an odd thing for AppleCare to do.