Estou usando o Ubuntu 14.04 e estava precisando da mesma coisa, então resolvi isso com alguns passos simples.
Eu iniciei o MySQL a partir do comando: mysql-workbench
Eu cliquei com o botão direito no ícone e o tranquei no iniciador
No terminal eu corri o seguinte:
gedit .local/share/applications/mysql-workbench-bin.desktop
Eu removi o caminho que estava apontando para /home/USER
Por fim, editei o Exec de mysql-workbench-bin
para mysql-workbench
Este é o resultado final:
[Desktop Entry]
Encoding=UTF-8
Version=1.0
Type=Application
Name=MySQL Workbench
Icon=mysql-workbench-bin
Exec=/usr/bin/mysql-workbench
StartupNotify=false
StartupWMClass=Mysql-workbench-bin
OnlyShowIn=Unity;
X-UnityGenerated=true
A única coisa que eu faria é garantir que você tenha os caminhos certos, além de que isso deve funcionar.