Unfortunately it looks like I would have to compile tcl from source to get a version recent enough to work (wants 9.0, ubuntu currently has 8.5).

Not only that, you'll have to compile some TCL modules too

;) Unfortunate? Yeah, a lot of people say stupid stuff like this -- I've been saying it for decade -- building your own GUI toolkit (Prima) is much harder :)

Even if I was willing to do that, I don't think my users would be.

If you don't want your users to jump through hoops (good idea), then distribute binaries good buddy :) http://citrusperl.com//http://cavapackager.com/