The error is certainly misleading.
You might not have delete rights for that directory.
I get "directory is not empty" when trying to delete a directory that has files or directories in it.
If I deliberately set the readonly attribute on the directory, I get "file access is denied".
Are the directories copied from a CD?
If so, they are usually read-only.