The developer of NmapFE for OS X hasn’t made a release since late 2004 and consequently is using an outdated version of Nmap. Outdated to the point it doesn’t work:

sendto in send_ip_packet: sendto(5, packet, 28, 0, 127.0.0.1, 16) => Invalid argument Sleeping 60 seconds then retrying

I’ve created an Intel build from CVS using nmap 4.20, which seems to work for me. It is available for download here. (link removed)

Update: Actually, this doesn’t work very well. I’ll compile something soon that does.