I've only used Ubuntu, but since it's based on Debian, it might work out. Have you tried installing postfix (which is all I touch right now) BEFORE uninstalling exim? If it satisfies the dependency for the web server, it's just getting to that point that is the problem, then you might be able to do it that way. I'm pretty sure that's what I did on my very first Ubuntu install, which also used exim as the default.

Alternately, you might be able to use some combination of options that lets you remove exim and add postfix in the same command, but I'm still learning the debian package manager, so I don't know if that's possible.