Minha reação intestinal diz inodes
Verifique seus inodes. Essas são a parte oculta do sistema de arquivos que mantém metadados sobre os arquivos.
df -i
Eu suspeito que você tenha muitos, muitos arquivos pequenos. Se esse for o caso - e observe que cada arquivo precisa de um inode - você pode usar inodes antes de usar o espaço de armazenamento real.