Hi,
we had a similar problem after the transfer of the database from an old to a new installed version. We solved the problem with the following command:
sudo -u www-data php /var/www/html/nextcloud/occ config:system:set mysql.utf8mb4 --type boolean --value="true"
sudo -u www-data php occ maintenance:repair
After that my contacts are working perfect. Perhaps this will help you.