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.