1 year and 3 months later... jessie, sid and wheezy-backports contain a new version of nmap (6.40-0.1 and 6.40-0.1~bpo70+1), but this bug remains open. Please, change the nmap --> python relationship from Depends to Recommends or Suggests.
I do not consider ndiff a "significant amount of functionality", the main program is nmap and works fine without python: http://www.debian.org/doc/debian-policy/ch-relationships.html#s-binarydeps
