Texmaker Shortcuts not working on Ubuntu 16.04

Install the Qt5 version of texmaker (at this date it is the one you get from ubuntu-software-center) and always run it from terminal using:

env UBUNTU_MENUPROXY= texmaker

or (a permanent solution)

Edit texmaker:

Open nautilus as root:

sudo nautilus

Navigate to usr/share/applications/texmaker , right click on it, properties, and change on Command texmaker %F by env UBUNTU_MENUPROXY= texmaker %F `

You don't have to install the older version, you just need to remove the appmenu package for QT5:

sudo apt remove appmenu-qt5

P.S. I am not sure if it can cause problems for other applications on your system. It didn't cause any problem in my end.

Regarding solution 2 of Vitor, you can also edit the launcher shortcut to TexMaker:

/usr/share/applications/texmaker.desktop

and change the line

Exec=texmaker %F

to

Exec=env UBUNTU_MENUPROXY= texmaker %F