Just a small update:
After some more testing, it seems that this problem repeats itself as I expected yesterday — if any groups user belongs to (not just the primary group) has any non-ascii symbols either in their name, or in "Active Directory Folder", this user cannot log in.