O problema é que a versão do System C IPC de fakeroot
não funciona corretamente nesta versão do Windows.
A solução é executar o comando:
sudo update-alternatives --set fakeroot /usr/bin/fakeroot-tcp
Depois de executar o comando uma vez, mk-build-deps
funcionará como esperado, para sempre.
(Minha resposta é baseada em uma postagem pelo usuário do Hacker News "danieldk".)