I had the same problem. After looking at:
I found out that when I'm deploying an application to the PDA using Visual Studio, it deploys also a folder I have in my project that don't contains code but some content files that I asked Visual Studio to copy to the output directory. I guess Visual Studio don't have permissions to override it, therefore the deploy fails, but not in the first time you are deploying this application.
To solve the problem you need to delete the directory. Maybe try to do it using a post build event.