Why would ping succeed but nmap fail?

Why does Nmap report "Host seems down" when a simple ping succeeds?

me@computer:~$ ping 123.45.67.89
PING 123.45.67.89 (123.45.67.89) 56(84) bytes of data.
64 bytes from 123.45.67.89: icmp_req=1 ttl=45 time=91.1 ms
64 bytes from 123.45.67.89: icmp_req=2 ttl=45 time=102 ms
64 bytes from 123.45.67.89: icmp_req=3 ttl=45 time=100 ms
^C
--- 123.45.67.894 ping statistics ---
3 packets transmitted, 3 received, 0% packet loss, time 2002ms
rtt min/avg/max/mdev = 91.136/98.182/102.417/5.022 ms

me@computer:~$ nmap 123.45.67.89

Starting Nmap 5.21 ( http://nmap.org ) at 2014-04-02 14:23 EDT
Note: Host seems down. If it is really up, but blocking our ping probes, try -PN
Nmap done: 1 IP address (0 hosts up) scanned in 3.04 seconds

Are Nmap's "ping probes" different from the command line ping?

Nmap sends many different probes to determine if a host is up. In your specific case, because you are running Nmap without root privileges, it cannot send ICMP Echo requests, which is what the ping utility uses. In this case, it tries to connect to port 80 and port 443, reporting the host as up if the connection is opened or rejected. Your target must have a firewall which is dropping all traffic to those ports.

To allow Nmap to find the system, try running it with root permissions. The sudo command is frequently used for this purpose, e.g. sudo nmap 123.45.67.89

ping can send ICMP packets because it is installed setuid to root, meaning that any user can run it, but it will run as the root user when they do. Setuid programs must be extra super careful about not letting regular users gain a shell through this extra permission. Nmap in particular cannot prevent this privilege escalation, so it should never be made setuid.

Yes they are different by default, ping is ICMP, and nmap ping sends a syn package to port 80 if I remember correctly, try using the -PE, -PM, -PP flags to make it do an ICMP ping