When this error is seen the local files/dirs can be inconsistent with those files on CVS server.
I agree that the first thing to try is:
1.
ditch your local working area (keep a backup copy of it) and checkout a clean latest version.
I encountered a situation where moving the local copy out of way and checking out a new clean copy did not solve problem. So . .
BE CAREFUL! Backup working area and files before editing them. Next thing to do is:
2.
Edit the CVS/Entries file and remove any problem files.
If that doesn't solve problem you may have to 3. login to CVS server and remove directories BE VERY CAREFUL!
The cvs add command changes files on server (yes, even without a commit).
When cvs add is done of a directory the cvs server creates directory on server. So if a cvs add is done of directories and commit is not done the cvs server is in a state where cvs add can conflict. In my case I added a directory which included some symbolic links to other directory in the tree. CVS didn't like that and command failed leaving my local copy and cvs server confused. I could not commit the changes in the broken working area and yet in a clean working area I could not cvs add the dirs before I removed them on the cvs server.