Yesterday I encountered a problem of files being kept back and not upgraded during an apt-get upgrade on debian lenny. The files were bind related.
The following command solved the problem enforcing dependencies to be upgraded also:
apt-get -o Debug:
kgProblemResolver=yes dist-upgrade
Probably bread and butter advice for most debian users, but will hopefully help someone else like me.