MySQL 5.0 не доступен ни для чего после Ubuntu 8.04 (hardy). 8.04 Server Edition по-прежнему поддерживается в течение нескольких лет, так что это может быть для вас.
Вот официальные пакеты по версии для 5.0:
$ rmadison mysql-server-5.0
mysql-server-5.0 | 5.0.21-3ubuntu1 | dapper | amd64, i386, powerpc
mysql-server-5.0 | 5.0.22-0ubuntu6.06.15 | dapper-security | amd64, i386, powerpc
mysql-server-5.0 | 5.0.22-0ubuntu6.06.15 | dapper-updates | amd64, i386, powerpc
mysql-server-5.0 | 5.0.51a-3ubuntu5 | hardy | amd64, i386
mysql-server-5.0 | 5.0.51a-3ubuntu5.8 | hardy-security | amd64, i386
mysql-server-5.0 | 5.0.51a-3ubuntu5.8 | hardy-updates | amd64, i386
mysql-server-5.0 | 5.1.30really5.0.83-0ubuntu3 | karmic/universe | amd64, i386