I finally got nMap working under Vista. I don't know if it was the latest version of nMap I installed (4.23RC3) or winPCap (4.02), or some other change to Vista (update). You do need to run it as an administrator to get access to the network card at the low level required by the tool.

I don't know when they added this, but in the 4.23RC3 the GUI is included and works well. The command line is still there in the background available for the power users. One nice thing about the GUI is that as you make changes, you see the command line that is going to be execute.