Can you please confirm your exact Alfresco version (you can extract snippet from startup log) ?
Ideally, you/we can narrow down the exact repeatable steps, to ensure that recent fixes to the VersionService also resolve your specific issue (or not).
IIRC, you're running Alfresco Enterprise, so please feel free to contact Alfresco Support (if you haven't done so already) to track your issue in more detail :-)
I am also facing same issue if try to upload.
Like I had doc1.pdf with 1.0 version if I try to upload minor/major version on that file I am getting error as Caused by: org.springframework.dao.ConcurrencyFailureException: Unexpected: current version does not appear to be 1st version in the list [workspace://version2Store/d788b9aa-d6aa-44a4-b43e-6562b75d5e91, workspace://SpacesStore/d319dddd-1917-4aaf-b815-750f3ca30904]
Almost same issue - then I save node and try to create version using JS I get the same error:
Caused by: org.springframework.dao.ConcurrencyFailureException: Unexpected: current version does not appear to be 1st version in the list [workspace://version2Store/d2c78435-ef7d-45fe-8533-e353e0be04ca, workspace://SpacesStore/c109c8a7-0408-497a-ae90-4400436117ac]
In my case exception was caused by broken node versioning. Version creationg always should be done at the end of transaction, and if you try to change node after version creating it will breake this node, and in future if you will try to create new version of the node or call getCurrentVersion() using VersionService it will return this error. To repair the node you can delete versionHistory of the node, maybe there are some other methods, but I don't know them.
Example of the wrong code in JS:
node.properties[...] = ...;