Indeed, I was not listening to what aptitude told me to do. I had renegade dependency from the old evolution-3.4.4 (libreoffice-evolution and libebook) which I had to uninstall first. After removing them manually, aptitude was able to install evolution-3.8.5.
