Comment # 1 on bug 1047849 from Wolfgang Bauer

Is the icon displayed as black square in the normal place (it should be in
Utilities) or in the search result too?

What icon theme?
It works as expected here with Breeze (only tested on the latest versions
though).

Try to delete the icon cache (~/.cache/icon-cache.kcache) and logout/login. It
might have become corrupted somehow.