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)