Eu encontrei a solução. O problema é que o mysql-workbench depende do mysql-client, que atualmente está no 5.5, então ele não será instalado com o mysql-server 5.6 instalado.
Portanto, para evitar o problema das dependências não satisfeitas, não iremos instalar o MySQL Workbench a partir do apt-get, em vez disso, vamos fazer o download e instalar sua distribuição binária.
Stpe 1. Faça o download
Acesse a página de downloads do MySQL Workbench, selecione o Ubuntu Linux como sua plataforma e baixe a versão correta para o seu Ubuntu.
Etapa 2. Instalação
Depois de baixar o arquivo .deb, basta clicar duas vezes nele e o Ubuntu Software Center será aberto. Se o MySQL Workbench não iniciar a instalação automaticamente, clique no botão Instalar e aguarde a conclusão do processo.
E você está feito! Você tem a versão mais recente do MySQL Workbench em execução no seu MySQL Server 5.6