Just the inspiration I needed!
I'd suggest a small tweak though - this current code works out what the slug should be by sanitising the query variable (which I believe could be anything coming from the URL rewrite) then looks up the category name and turns that into what should be the slug.
However the actual slug doesn't always equal the sanitised name as you can edit the slugs in the admin.
The following tweak will get the actual slug assigned to that category from the database:
$cid = absint( get_query_var('cat') );
$cat = get_category($cid);
$file = TEMPLATEPATH.'/category-'.$cat->slug.'.php';
return (file_exists($file)) ? $file : $template;
It shouldn't need sanitising as its already been cleaned before writing to the db.