Se coreutils não estiver instalado, seu sistema será seriamente escolhido.
O /bin/date existe e funciona? Se sim, “apenas” o seu banco de dados de pacotes está corrompido. Nesse caso, restaure /var/lib/dpkg/status de um backup - por exemplo, /var/lib/dpkg/status-old ou um dos arquivos /var/backups/dpkg.status.* (lembre-se de descompactar os arquivos *.gz ).