This error appears when a corruption in the cache arises, caused by a bug in Magento.
We see this error mostly on shops that experience high traffic, causing a rare condition in the caching mechanism.
The developers from Convenient and AmpersandHQ fully debugged this issue and came up with a patch that should solve this issue once and for all.
You can find detailed information about how to solve this issue on the GitHub page of Convenient.
This issue is as far as we know a Magento 1 only issue, although a very small group of developers working on Magento 2 have notified us of having the same issue appear in Magento 2.
Update: So it seems it could help changing the permissions on certain a PHP file if the convenient patch does not fix this issue.
Update 2: Adding other suggestions to fix this issue from Magento explorer.