When I try to delete an album from the admin section, I am getting error:

Warning: rmdir(/home/mindoutp/public_html/gallery/albums/Voodoo_Therapy_Mar_03_07/) [function.rmdir]: Directory not empty in /home/mindoutp/public_html/gallery/zen/class-album.php on line 278

Warning: Cannot modify header information - headers already sent by (output started at /home/mindoutp/public_html/gallery/zen/class-album.php:278) in /home/mindoutp/public_html/gallery/zen/admin.php on line 75

The album folder had rights: drwxrwxr-x which I think is more then enough.

Though I can login to the account from SSH and "rm -rf" the folder and it works. Though, doing it from the admin section would be nice.

Look via FTP to see what is in your folder. If you have a file other than an image, it won't get deleted and will prevent the folder from being deleted. I know that often I have thumbs.db in the folder thanks to Windows. Have to delete this manually.