If you get the following warnings, and there are no icons in Evolution, you probably have a non-existent theme selected in the gnome theme manager.
Gtk-WARNING **: Unable to locate theme engine in module_path: “qtengine”
One of the probable causes is that some themes get deleted/updated when installing gnome updates.
This can be fixed by running gnome-theme-manager and select a different, existing theme.