I totaly share your frustration. arg!!

The problem lies in the menu package.
update-menus is for some reason not installed. (at least not on my machine)

My solution was to unpack the menu package.
ar x menu<somthing>.deb
tar -zxvvf data.tar.gz
Copy update-menus to /usr/bin
Do a chmod a+x /usr/bin/update-menus (as seen in the postinst script)
apt-get install joe

Now I'm also able to do a:
apt-get install menu
without failure. And start som other app's that did not work.)

Best regards
staale