Are you using some user login extension ? (eg. http://www.mediawiki.org/wiki/Extension:LDAP_Authentication)
Have you been playing with isValidUserName(), $wgLegalTitleChars or $wgMaxNameChars?
May have someone deleted the user table entries? (check in mysql that the user table entries are present)