Our new depcheck detects broken dependencies only for those builds, which were part of the <tag>-pending set. But it does not detect when an existing package (currently present in e.g. fedora or updates repo) gets broken by that update.

Example here:
https://admin.fedoraproject.org/updates/FEDORA-2014-12246/at-3.1.16-1.fc21

The problem is that there used to be:

at-3.14
at-sysvinit-3.14 (subpackage, requires at-3.14)

Now there is:

at-3.16

But that doesn't obsolete at-sysvinit. Therefore at can be easily installed at both versions, but once the update hits stable, at-sysvinit will become uninstallable - it will have broken dependencies (no at-3.14 build available). That's caused by the fact that Fedora repositories keep only the last version of a package available, the old ones will get removed (unless, of course, at-3.14 is in fedora and at-3.16 goes to updates, then it would work. But if both are in updates, the problem occurs).

Our old depcheck correctly detected the problem:
http://autoqa.fedoraproject.org/results/878234-autotest/virt07.qa/depcheck/results/at-3.1.16-1.fc21.html

The new depcheck did not:
https://taskotron.stg.fedoraproject.org/resultsdb/results/329579

A simple testcase scenario to cover this could be like this:

name: Broken dep for an existing package
description:
    Library got updated but the dependant app didn't
expected_outcome: fail

current_repo:
  - envra: mojito-1.0-1.fc19.noarch
    requires: libmint = 1.0

  - envra: libmint-1.0-1.fc19.noarch
    provides: libmint = 1.0

update_repo:
  - envra: libmint-2.0-1.fc19.noarch
    provides: libmint = 2.0

I think there are two areas we need to fix (but don't take me too seriously, I'm not completely familiar with how the new depcheck works):
Check dependencies for all packages, not just the ones in <tag>-pending. That would be like this:
# Check all packages in current_repo and find out that nothing has broken deps (or mark down those which have broken deps). In this case, mojito-1.0 and libmint-1.0 are both fine.
# Add update_repo to depcheck, and check everything once again. Compare with previous results. If something is broken that wasn't broken before, we have found a problem. If the broken package is not part of update_repo, it will get tricky to find out which update caused it. Maybe run again and go one by one update from update_repo to find to culprit? In our case, we would detect that mojito-1.0 gets broken.
Configure libsolv to consider only newest package versions while resolving. There is a yum configuration to do this, I hope there is one for libsolv too. This is crucial, because otherwise libsolv will see both libmint-1.0 and libmint-2.0 as seemingly being available, and it will not detect any error. But in reality, libmint-2.0 will replace libmint-1.0 and it will be the only version available.