I have a foggy memory of an issue just like this. It was related to “saved searches” on the list view. That’s why it was user specific.
Let’s try and clear the saved searches from those users.
Try entering this as your browser’s URL:
http://localhost/index.php?action=index&module=Contacts&searchFormTab=advanced_search&query=true&clear_query=true
Change that “localhost” to be your server URL (like my.company.com).
This has to be done for each user that shows the error.