Rodando
sudo env UBUNTU_MENUPROXY= texmaker
funcionou para mim!
Texmaker não reconhece atalhos como Ctrl + F para Localizar ou Ctrl + O para Open. Este era um problema conhecido em versões anteriores do Ubuntu, mas a solução comum para essas versões não funciona para o Ubuntu 16.10.
Solução tentada:
Executando o texmaker com o UBUNTU_MENUPROXY
desativado.
env UBUNTU_MENUPROXY= texmaker
Rodando
sudo env UBUNTU_MENUPROXY= texmaker
funcionou para mim!