on ubuntu: sudo apt-get install nmap nmapfe

Edit the menu for Zenmap: system -> preferences -> main menu -> Internet -> Zenmap -> properties
make command: gksudo zenmap
(this will run the applicaition with root privs for scanning)