This was annoying and slightly confusing. Some folders would delete OK (and sync online) but others would re-appear. This was on Windows 7.

Solution: Right-click and "View on" which opens your browser. It turns out, in my case, there were two files in the folder which, for whatever reason, hadn't sync'd to my computer and made the folder look empty. I deleted them using the browser interface and was then able to delete the folders permanently from my computer.