MySQL 5.0 -> 5.1 upgrade, table upgrades taking a very long time

The main question is, how can I upgrade these tables and get the data online more quickly?

The simple answer is run mysql_upgrade.

Does using myisamchk with something like "myisamchk --sort-recover --analyze --sort_buffer_size=256M --key_buffer=256M --read_buffer=2M --write_buffer=2M tablename" upgrade the table (i.e. not using the keycache method)?

No.

Can I safely kill the debian script and upgrade the tables with a more efficient method?

I need to know more details about this script.

The server was initially started with a key_buffer_size of just 16M. I've since corrected this by setting the global variable, but is it possible that the debian script's session is still using some smaller value? If so can I alter it?

You can do it for a session:

mysql> SET SESSION key_buffer_size = ... ;

Turns out the debian script just the standard init script which checks for upgrade needing tables, thus killing it wasn't a problem as it simply re-runs on init.

The key buffer value wasn't the problem, as I suspected it was the keycache method it was using to repair the table - it's simply too slow for this much data.

Once we 'set global myisam_max_sort_file_size=21474836480;' and restarted mysql, it started using the sort method which is much faster. But then on another table it went back to keycache so I raised it to 80G and restarted again.

All tables are now upgraded.