Nautilus requires gnome-icon-theme-legacy for the emblem icons (emblem-noread and so on), so this should be added ad a Requires. Rhythmbox pulls in gnome-icon-theme-legacy on a standard desktop build, but it is best not to leave this to chance. Rawhide, F20 and F19 are affected.
Created attachment 878528 [details] f20 patch
Created attachment 878529 [details] rawhide patch
Created attachment 878530 [details] f19 patch
Upstream patch merged, will be fixed in a future 3.12.1 release.