You'll often need multiple templates anyway, irrespective of whether you use frames or not - its generally a lot cleaner to have a bunch of small templates that you put together (header, footer etc) than use a big HTML::Template with lots of 'if's etc. - nicer on your HTML people too :)

Generally in this situation, where there are multiple frames updating at different times, I prefer to use a single script/Template combination for each frame - main.cgi, menu.cgi, info-frame.cgi etc.
One thing you might consider is <iframe>, which is pretty well supported now and can clean up your layout considerably - much nicer than using DHTML (which should never be implemented using *shudder* 'LAYER' btw - but that's a whole other can-o-worms...).

Cheers,
Ben