Before you can remove a directory, you must remove (unlink(2)) all files from that directory first. Note, even if the directory looks empty, remember to check for hidden "." files, especially ones created by emacs(1), cvs(1) etc.
2 pages link to ENOTEMPTY: