If they right-click on the Inbox and select Open when it is in that state, do they then see mail? If so, you may want to check if IBM Technote 1965120 applies. 

If the technote does not apply in your case, that is, there is no unnamed folder in the mail files, the solution provided in this case would still be worth trying:

1)  Create a temporary folder. 

2)  Move the mail that appears in the Inbox to the temporary folder. 

3)  Delete the Inbox through the Designer client. 

4)  Do a refresh design on the mail file. 

5)  Move the mail that is in the temporary folder to the new Inbox. 

6) Delete the temporary folder. 

you can also use Lotus script to rebuild the inbox.  See the technote:

How to Rebuild a Notes Mail inbox

http://www-01.ibm.com/support/docview.wss?uid=swg21104973

From Domino Administrator's tasks list ... is anything swallowing up the server CPU? Maybe a full text index refresh, or Indexer reporting it's refreshing a view?

Because if you're overloading the server this is pretty much what it'll look like.

First recommendation there: launch another "Update" task.

Are the mail files in question on the server? Or local replicas? How many documents do the users in question have in their Inbox?

If there are a lot of emails, you might test by moving 'most' out of an inbox to a temporary folder, and see how the inbox acts with only 'new' mail...

I'd seen something similar in the past for users that had thousands of emails in their mail-on-server inbox - takes a bit for the server to index... I've since moved to locally managed replicas which solved a couple problems..

This is all happening on the client.  The server is huge and has no issues at all.  Does not matter if the client is connected to the older 8.5.3 server or the newer 9.0.1 server.

The users mailboxes have been recreated manually on both servers with no change on the client side. 

I have also posted two other responses that do not appear to be listed on this forum.

PMR is open for a month.