I was able to recreate the error message although I had to interpret settings. Some may be applicable to your environment/situation. Short story is to check that users have correct Selective Access for the Lists flagged as such and next check correct Access to Version. If its set to NONE then you could get this error. I suspect that the "sometimes" it works phenomena is related to Versions changes from a read/write list item to one without access.
Steps to Recreate:
First even with Full Access IF Selective Access is flagged for a list a user or team needs to be set to Read or Write Access.
In my test I set the Parent level list to Selective Access and set my self as Read Only. This Profile is inherited by to the child list.
Next I set User Security > Role > Version for Actuals to None
Then ensured that in my Module Versions was set to All
Lastly I tried to add a new list item. This resulted in warning message.
If this still doesn't resolve it please send along exact steps to recreate along with scrn shots of User secruity, List and module settings.