Comment 52 for bug 1386111

While removing appmenu-qt5 solves the issue, it also removes the unified menu which isn't so nice. For me, simply downloading and installing the qt4 version of texmaker (for Ubuntu 15.10, works just fine on 16.04) from the texmaker homepage solved the issue. Now I still have the unified menu, shortcuts working plus the latest version of Texmaker :)
The version I used for this: http://www.xm1math.net/texmaker/texmaker_ubuntu_15.10_4.5_amd64.deb

Of course, a proper fix for qt5 would still be nice.