There are several mass filename rename utilities on the net. Most of them will do what you require. Just batch rename all your folders.. i.e. replace " " with "-". These are windows only programs though.
As for updating the tables, there are a few options:
Perhaps you could find a database management console for mysql that can batch rename/modify all your folder names in the database (using regular expressions perhaps) I'm not sure about it though.
Alternatively you could SQL dump the albums table, regex the folder names using a competent text editor, and put the modified SQL data back into mysql?
Another, albeit more elegant, solution would be to write a small php script which reads all the album data, modifies it according to your requirements, and then updates the table. I'd go with this route if I were you.
This is just my brain dump as to how to achieve what you want to do with your albums. Nothing concrete, just some ideas.
BTW, I just found out, zp works well with hyphens. I.e., if your folder is named "my-album", zen photo will show the name as "my album"! This gives you the both of best worlds! I'm using todays nightly build.