I discovered this while doing automated testing of upgrades from Debian Lenny to Squeeze. A few packages in Debian still got circular dependencies, and it is often claimed that apt and aptitude should be able to handle this just fine, but some times these dependency loops causes apt to fail.
An example is from todays upgrade of KDE using aptitude. In it, a bug in kdebase-workspace-data causes perl-modules to fail to upgrade. The cause is simple. If a package fail to unpack, then only part of packages with the circular dependency might end up being unpacked when unpacking aborts, and the ones already unpacked will fail to configure in the recovery phase because its dependencies are unavailable.
In this log, the problem manifest itself with this error:
dpkg: dependency problems prevent configuration of perl-modules: perl-modules depends on perl (>= 5.10.1-1); however: Version of perl on system is 5.10.0-19lenny2. dpkg: error processing perl-modules (--configure): dependency problems - leaving unconfigured
The perl/perl-modules circular dependency is already reported as a bug, and will hopefully be solved as soon as possible, but it is not the only one, and each one of these loops in the dependency tree can cause similar failures. Of course, they only occur when there are bugs in other packages causing the unpacking to fail, but it is rather nasty when the failure of one package causes the problem to become worse because of dependency loops.
Thanks to the tireless effort by Bill Allombert, the number of circular dependencies left in Debian is dropping, and perhaps it will reach zero one day. :)
Todays testing also exposed a bug in update-notifier and different behaviour between apt-get and aptitude, the latter possibly caused by some circular dependency. Reported both to BTS to try to get someone to look at it.