Damn, CKRename is perfect except it is not recursive. It even gives a preview of the results so you know what you are getting, very sweet feedback feature.
[edit]
It did the job though, I only had under 20 directories to do. Recursiveness would guarantee that I didn't miss any though!
