O cartaz original, Graubart, conseguiu resolver seu próprio problema . O sistema Ubuntu estava sendo chroot ed de outro sistema não-Ubuntu. Mas o comando dpkg foi acidentalmente emitido fora do chroot. Fazendo chrooting no sistema de arquivos no qual o Ubuntu foi instalado, o Graubart conseguiu executar dpkg sem problemas.
Ok, descobri por que não encontrei o dpkg - ele está em chroot e eu estava em chronos @ localhost. Mudou para chroot e lá estava! Típica erro greenhorn, suponho.