Comment 6 for bug 533638

It looks like this problem was just fixed in findutils 4.4.2-1ubuntu1....
From the changelog.Debian.gz file:

findutils (4.4.2-1ubuntu1) lucid; urgency=low

  * Don't depend on dpkg (>= 1.15.4) | install-info.
    The purpose of this dependency, pursuant to a "should" directive in
    policy, is to ensure that /usr/share/info/dir is properly rebuilt during
    upgrades. Unfortunately, this dependency introduces a loop on upgrades
    from Ubuntu 8.04 LTS that can't be broken without the use of
    --force-depends:
      libc6 Depends: findutils (>= 4.4.0-2ubuntu2)
      findutils Depends: dpkg (>= 1.15.4) | install-info
      dpkg Pre-Depends: libc6 (>= 2.11)
    Since it isn't the end of the world if the info directory isn't rebuilt
    when doing a partial upgrade of just findutils, this is the safest place
    to break that loop. We can drop this change after Ubuntu 10.04 LTS is
    released.

 -- Colin Watson <email address hidden> Tue, 09 Mar 2010 13:15:12 +0000