I discovered upgrading a client from 3.0-RC3 to 3.1.9 that if the username contains certain non-Latin characters (the board is Danish) these users could not login. In addition, in the ACP the username could not be found. After much analysis I determined that the value for username_clean in the database was different in the upgraded database compared with running username through utf8_clean_string. See my solution here:
There is likely a general problem here. A utility can clean these up but perhaps the database_update.php program needs to recalculate these for all users, at least if a language that uses more than basic Latin characters is used.