Попалась мне интересная задача, если кратко: вычистить dpkg list от пакетов (пусть начинаются на test-).
Я бы aptitude попробовал говорят у него резолвер зависимостей лучше.