I think tag clouds are good for SEO, but I wouldn't put the cloud on every page. Tags in general are good for SEO because they are hand edited categorized same as a person edited directory and hence search engines value this. Linking together related pages like Tag Cloud is key to getting indented search listings in Google.
I wouldn't spend much time tagging old content though, maybe just concentrate on keywords you want to rank for.

I've got some ideas up my sleeve on how to make tag pages better for SEO, but I'll let you know more once I build it into a plugin. Stay tuned.