convmv
convmv is a small tool, with a somehow misleading name. It is described in detail in http://www.j3e.de/linux/convmv/man/.
Basically, it can rename an entire file-structure from one encoding to another. The most common usage will be as follows
convmv -f iso8859-1 -t utf8 -r <directory_to_rename>
Which will list all the changes that convmv proposes to the file-structure. Beware that the output looks misleading. Convmv will rename the subfolders, but the output will first show the changes to the filenames within the not-renamed-directory. The folder rename is output last.
Once you are satisfied that the files will be re-encoded correctly, run
convmv --notest -f iso8859-1 -t utf8 -r <directory_to_rename>
which will rename the files for real. In spite of the name convMV, the tool cannot move the files, only rename them.