Wow, I have absolutely the same problem. I'm using IIS 6.0/ If I create an album, put some pictures in it, and then try to delete it, pictures dissapear, but the album stays alive with error jhunnicutt wrote. I thought it was something wrong with permissions, so I gave IUSR_SERVER (SERVER is the name of my PC) full permissions on "albums" dir, but nothing changed.
As I understand, IIS is not officially supported by zenphoto's dev-team. I miss my Carmic Coala Server with Apache on it :'-(