I am having a similar issue.
I have two computers at home and installed on both of them Ubuntu 10.04. But in one (laptop) I just upgraded through the Update Manager from 9.10, while on the other (desktop) I did a full reinstall with a CD (and forgot to backup the Evolution data).
Well, the results have been different on both, regarding Evolution. In the laptop, I can still see and download emails from my job's Exchange Server. While on the desktop, Evolution seems to connect and see the server, but nothing is downloaded. I even removed the
account a couple of times, to see if I had mis-configured it.
My next step is to backup the Evolution data and setup from the laptop and copy it to the desktop. I will let you know the outcome.
Hopefully, this piece of information might help you.
Update (5/26/2010)
Just tried it and worked!
I backed up my Exchange account from my laptop, and restored it into my desktop Evolution program. Then I pressed "Send/Receive" and new emails where downloaded.
Note: I've also been unable to get IMAP to work between the latest Evolution and Exchange. Evolution IMAP works fine against other servers... – Brian Knoblauch – 2010-01-27T20:12:22.163