Use o aptitude em vez do apt-get. É mais inteligente. Ele não só irá lidar com o downgrade de pacotes conflitantes para você, mas fará uma série de recomendações perguntando qual dos vários possíveis cenários de trabalho sugeridos você gostaria.
sudo aptitude install myNewPackage
Se você ainda não tem aptidão na sua máquina, use-a com
sudo apt-get install aptitude