There is one more possibility which I ran into.
In my case, I could not even take Ownership of the folder. When applying the change, an 'Access is denied.' error was presented.
The problem for me was that I had included this folder I was trying to delete in my Pictures Library Locations.
Brief explanation:
If you browse to any Library, you'll notice at the top of the Explorer window it says "Includes: 3 locations" (or some number). Click that and it shows you the list of folders it aggregates to form the Library itself.
The folder I was trying to delete was here, and once it was removed, the folder can be deleted (or it may delete itself automatically if it was set to be deleted as part of an application Uninstall previously)
Hope this helps someone :) Certainly it's a bug.