Para o benefício de outras pessoas, aqui está um cenário em que esse problema ocorreu para mim: usar o repositório de encaixes Jenkins mais recente , que é baseado no Debian 8 "jessie".
Eu executei as instruções normais de instalação mono, incluindo
apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 3FA7E0328081BFF6A14DA29AA6A19B38D3D831EF
echo "deb http://download.mono-project.com/repo/debian wheezy main" | tee /etc/apt/sources.list.d/mono-xamarin.list
Em seguida, o apt-get install -y mono-devel
falhou com dependências não atendidas.
Eu tentei recarregar a imagem do docker e executar a instalação sem os dois comandos acima. De repente, funcionou.
Aparentemente, o repositório padrão de terceiros para o mono não é necessário com a imagem mais recente (de 30 de março de 2016) da Jenkins.