I've just tested running zenmap and it does work for me. What output do you get when you run it from the terminal with the command zenmap-kbx?

$sudo zenmap returned 'no zenmap command was found'.
Although installation finished without any (visible) problems.
Of course, kali is fully updated and upgraded.

The command is zenmap-kbx not zenmap

Thank you for your tip!

Eventually, it seems to be working (although not thoroughly tested), but:

• Application delayed starting for some time making me wonder if it is going to start at all, and before starting the following message appeared:
• /usr/local/lib/python2.7/dist-packages/zenmapGUI/MainWindow.py:116: GtkWarning: Unable to locate theme engine in module_path: "adwaita",
  HIGMainWindow.init(self)

No idea what it means and why it was produced and most importantly, what is the impact to zenmap's functionality (if any of course)...

Thank you again for your time.

That messages are only warnings coming from the gtk window library, not zenmap itself. It doesn't affect zenmap

I'm closing this as it seems it's working