I had exactly the same problem as Kurt on my x86 machine; I had just done a fresh install of lenny, changed my sources.list to squeeze and then done a dist-upgrade; like Kurt, hal failed to configure properly.
So I left the problem as it was and rebooted. Then aptitude was still in a state to upgrade hal and its dependencies, only this time it worked fine. Don't know if that helps. Kate
