Se você não pode atualizar para um Ubuntu mais novo (por exemplo, 10.10), você pode pegar uma versão mais antiga do mysql-workbench. Parece que o link tem uma lista de versões mais antigas. Isto sugere que o mysql-workbench-oss-5.1.18a-1ubu904 -i386.deb pode funcionar.