Você pode obter uma lista de pacotes retidos reais com:
dpkg --get-selections | grep hold
Outro método de solução de problemas pode ser usar aptitude
em vez de apt-get
para tentar instalar seu pacote:
sudo aptitude install valgrind
O aptidão desistirá menos facilmente e tentará encontrar soluções que possam envolver a modificação de outros pacotes. Pode dar-lhe mais explicações sobre o problema e opções para corrigi-lo.