I had this problem on Ubuntu 12.10 using evolution 3.6.0-0ubuntu3, with libmapi0 1.0-2.
Installing libmapi0 1.0-4 from the link mention in post #24 above solved the problem. Pleasantly, I just did a straight install over the top of the existing version, via dpkg -i, there were no dependency problems.
I had this problem on Ubuntu 12.10 using evolution 3.6.0-0ubuntu3, with libmapi0 1.0-2.
Installing libmapi0 1.0-4 from the link mention in post #24 above solved the problem. Pleasantly, I just did a straight install over the top of the existing version, via dpkg -i, there were no dependency problems.