Gah.
[jake@jace]/bin% ls -lhd /bin
lrwxrwxrwx. 1 root root 7 May 22 2012 /bin -> usr/bin/
Eu estou rodando o Fedora 17. Aparentemente, /bin é um link simbólico para /usr/bin . E é claro (e com razão) find e locate ignoram os diretórios com links simbólicos para evitar a poluição resultante.