I have reproduced the problem with aptitude 0.4.11.11-1ubuntu10 in lucid following the steps described by Wesley in comment 25 and have verified that the version of aptitude 0.4.11.11-1ubuntu10lucid1 in -proposed fixes the issue.
I have reproduced the problem with aptitude 0.4.11.11-1ubuntu10 in lucid following the steps described by Wesley in comment 25 and have verified that the version of aptitude 0.4.11. 11-1ubuntu10luc id1 in -proposed fixes the issue.