you skipped steps recommended in the release notes..
http://www.debian.org/releases/lenny...rading.en.html
4.5.4. Upgrade apt and/or aptitude first
I would proceed more like the following.
change your sources list
aptitude update
aptitude keep-all
aptitude install apt aptitude
aptitude upgrade
aptitude dist-upgrade
There may be other things you should to do to prepare for your upgrade..
I strongly suggest you read the upgrade seciton of the release notes before proceeding,