Unclear why aptitude marks package as broken

I have a situation where aptitude marks a package cgroup-bin as broken:

$ aptitude search '^cgroup-bin$'
pB  cgroup-bin ...

In its UI, aptitude provides the following explanation:

Some dependencies of cgroup-bin are not satisfied:
* cgroup-bin depends on cgroup-tools

Both dpkg -l cgroup-bin and dpkg -l cgroup-tools issue dpkg-query: no packages found matching ... because neither package is installed.

Both apt-cache policy cgroup-bin and apt-cache policy cgroup-tools identify version 0.41-6 from the Debian repository as candidate versions.

aptitude show cgroup-bin lists these (relevant) dependencies:

Depends: cgroup-tools

aptitude show cgroup-tools lists those:

Breaks: cgroup-bin (< 0.40~rc1-3~)
Replaces: cgroup-bin (< 0.40~rc1-3~)

I have another machine which has the same properties but where the package is not marked as broken.

What is going on here? Why is package cgroup-bin marked as broken (when from the dependencies it would seem that versions 0.41-6 can live in unison) and how can I remedy the situation?