Access Web App error "We couldn't retrieve the items to list here"

We are receiving reports that many users are encountering an error "An error occurred. We couldn't retrieve the items to list here." when navigating views in their Access Web app on Office 365 (O365).

The Access developers are aware of the problem, a fix has been made and is rolling out. Most tenants will be fixed this evening. A small portion of tenants may not receive the fix until early next week. We will update this post if there are any changes.

Update 5/23/14: This issue should now be resolved for all tenants.