On a Plone 5.1.5 site which was migrated from 4.x I was experiencing the same problems. When a @@history page was it hit, after a couple times it would result in a Client has seen newer transactions than server! exception. Shortly after the initial exception multiple instances would return a ConnectionStateError, which caused an outage on the site.
The site was not running from RelStorage, but in our migration notes we had noted to reindex the catalog. This was not done on the live site. The fix recommended by @cekk fixed the exception we were experiencing. 