This occurred for us after a Parallels (9) update. Nothing seems to fix the issue short of a downgrade. We tried updating the parallels tools, changing the OS versio, starting with fresh VMs -- but nothing worked short of a downgrade.
Note that in our case, the issue only occurs when cloning on to the shared host filesystem (which we must be able to do). This fails after the update with Ubuntu versions 12.04 up to 13.10.
Sadly, Parallels has been astoundingly sloppy with the shared host FS. We may be forced back to virtual box at this rate.
One other possibility is to just set up an NFS export on your host and use that to share files rather than bothering with the shared filesystem. This seems to work ok for us. Here's a gist that shows how to set it uo: