You'll need to restore your database (or at the very least, your groups table) from a time prior to this issue, as managing the database directly (especially with such a large set of data) is impractical. You may have to manually add users who were created between the backup time and the restoration time to the proper groups if you choose to only restore the groups database table.
I attempted to identify this issue with this post, which went unanswered:
do your users not belong to any groups?
And further, you specified there was no problems with groups in your later posting, specifically indicating that users are in fact in groups:
Yes, all members are assigned to a group.
Which they are not, as the system reported with the error you supplied.
