>Couldn't find any package whose name or description matched "mysql-server5.0"В данном случае не принципиально, но буржуйский таки стоит выучить хотя бы на примитивном IT уровне.
>invoke-rc.d: initscript mysql, action "start" failed.
Итого запустить не удалось, а значит нужно искать причины в логах, как вам и сказали выше.
>В /var/log/mysql/ вообще ничего нет, совершенно пустой каталог
Неудивительно, откуда взяться бинарным(а в дебиане именно они там лежат) логам, если сервер вообще не смог запустится. Какое табу вам запретило проверить содержимое /var/log/mysql.err и /var/log/mysql.log?