I have recently got a new laptop after my previous baby died.
However, moving my evolution mail three times seemed to throw the indexes out and I kept getting sync errors.
To solve this, run the following command in the parent folder (~/.evolution/mail/) and re-open evolution it will re-index all your evolution mail files / folders.
[code]
find . -name "*.index" -exec rm -f {} \;
[/code]