First, I'm not embarrassed to admit when I made a mistake. So, with that being said, my mistake was editing .zenmap/zenmap.conf in my home directory. Making the edit under roots home directory fixed the issue.
edurenye correctly identified the root of the problem. The python-gtk2 package won't come back in Ubuntu, hence I marked the task as Won't Fix. The zenmap is likely to be reintroduced after a Python 3 version will be made available.
All of the above also applies to Debian, where zenmap has been dropped too. As the latest version of zenmap in Ubuntu was a sync from Debian, the right place where to reintroduce the package will likely be Debian.
The following packages have unmet dependencies:
zenmap : Depends: python (>= 2.5) but it is not installable or
python-pysqlite2 but it is not installable
Depends: python-gobject-2 but it is not installable or
python-gobject but it is not installable
Depends: python-gtk2 but it is not installable
Depends: python:any (= 2.7.5-5) but it is not installable
E: Unable to correct problems, you have held broken packages.