Hi. One thing that jumped out at me in your message is:
0 upgraded, 4 newly installed, 0 to remove and 278 not upgraded.
It looks like you have a very outdated box . Have you considered
running apt-get dist-upgrade? If you don't want to do that, try running
apt-get -u dist-upgrade to see what packages will be upgraded. You
could have another package that's not getting upgraded to the required
version for exim4.
I recently upgraded to exim4 and didn't see your problem. My system is
kept up to date with regular apt-get upgrade or apt-get dist-upgrade
commands.
Remember, this is just a wild guess.
Kenny
