I found this link. http://www.go-evolution.org/FAQ#Why_does_Spellchecking_not_work.3F which bacially says, "Make sure you have gnome-spell >= 1.0.5, aspell and aspell-XX (where XX is your locale, for example aspell-en for US English or aspell-en-uk for British English) installed". Evolution does not use myspell, ispell nor openoffice dictionaries.
Restart Evolution and they should all be there. I found I didn't have gnome-spell, probably because I am using KDE.