Is it all users or just a few, and if it is just a few are they maybe filtering their emails, I had this happen to a user before he was filtering so that he only saw new messages.
I hope it is this simple for you as well.
Hope this helps
yes, have them check at the top right under view, there they can filter by all messages, or unread messages, etc.
also if they have subfolders in their inbox they need to click the plus sign by their name to see the subfolders.