dpkg problems

[Kenny Hitt]

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