It seems there is a bug in MySQL which is causing restores to run very slowly (hours instead of minutes)
http://bugs.mysql.com/bug.php?id=33057 [1]
The bug is fixed in release 5.0.67 [2]
But Ubuntu hasn't updated yet....
Fortunately this bug is specific to the command line client.
Workaround: use the MySQL Administrator GUI instead.
Links:
[1] http://bugs.mysql.com/bug.php?id=33057
[2] http://dev.mysql.com/doc/refman/5.0/en/releasenotes-cs-5-0-67.html