Went ahead and spoke with my VAR about it. He stated that it may have something to do with the following bug:
1. Right-click File Types in vault and enable 'Do not allow duplicate file names in this file vault'. 2. Remove add file permission for a folder in vault. 3. Try to move a file into this folder - move is prevented - but incorrect warning shows: 'The file name: which needs to be unique in the file vault: has been used before.' - Also seen if lacking Delete permission in source folder (i.e. to move you need delete permission in source folder, add permission in target folder) - If duplicate file name setting is disabled in vault - correct warning is shown when move is prevented: 'You lack permission to process one file'
That turned out to be the quick, and was much quicker to hunt down the culprit workflow permissions.
The error your getting is throwing me but sounds like the users are missing the "Add or rename file" permission. I would check the user and group folder and especially the state permissions.
It ended up being a delete permission for the source folder.
Didn't click until I saw that SPR how a "Cut/Move" operation require delete permissions in source folder, and add permissions in the destination folder.
I have a user getting this same error on checkin and it is identical circumstances with the files.
See SPR 539979.
My issue was that I didnt have the delete permissions in the source folder though I did have the add permissions in the destination folder.
Its an easy fix. :-)