Comment 133 for bug 831768

aptitude_0.6.6-1ubuntu1.2_amd64 from precise-proposed fixes this issue for me.

I checked by trying to install wine. The dependency resolution only grumbles about one “recommends” which can't be resolved, which is probably okay. Before it would try to remove (almost?) every package installed.