Comment 11 for bug 31057

Thanks guys. I also had the same problem. With the help from this thread I determined that resolvconf was installed together with mailx.

Removing resolvconf did the trick. One thing however, you also need to remove all the configuration files that go with it otherwise the system will come up with an error message when booting up. Which you can safely ignore, I guess. Error caused by /etc/init.d/resolvconf.

To remove the configuration files use:
aptitude remove resolvconf_