From which version did you upgrade? Could it be that you haven’t upgraded in a long time?
Password hashing was changed from MD5 to BLF-Crypt if I remember correctly.
You should do then a rollback, login, change all passwords of all users, and then do the upgrade again.