Your Ping command is missing the capabilities to open a raw socket. Does it work with a non-root user? Is is suid root?
Note that, in Debian, /bin/ping is provided by two different packages, iputils-ping and inetutils-ping. Find out which one you are using, try to reinstall it, and/or try to replace it by the other package.