PPA: 3.19.5+git20160204.867a153-0ubuntu1~ppa1
Searching for "frozen" (looking for Frozen Bubble, you know, for testing) returns no results.
From the logs it looks like Frozen Bubble was found though, but maybe the icon is missing:
(gnome-software:4989): GsPlugin-WARNING **: vbaexpress 7 2 4 2 4 / 19 -> 53
(gnome-software:4989): GsPlugin-DEBUG: ubuntu-reviews setting rating on vbaexpress to 53%
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::apt(gs_plugin_add_search;gs_plugin_refine)
APT: gs_plugin_refine
(gnome-software:4989): Gs-DEBUG: search cancelled
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::appstream(gs_plugin_add_search)
(gnome-software:4989): As-DEBUG: run 0x2012990~appstream::search
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::ubuntu-reviews(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::apt(gs_plugin_add_search;gs_plugin_refine)
APT: gs_plugin_refine
(gnome-software:4989): Gs-DEBUG: search cancelled
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::appstream(gs_plugin_add_search)
(gnome-software:4989): As-DEBUG: run 0x20129e0~appstream::search
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::ubuntu-reviews(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::apt(gs_plugin_add_search;gs_plugin_refine)
APT: gs_plugin_refine
(gnome-software:4989): Gs-DEBUG: search cancelled
(gnome-software:4989): Gs-DEBUG: search cancelled
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::appstream(gs_plugin_add_search)
(gnome-software:4989): As-DEBUG: run 0x2007b20~appstream::search
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::ubuntu-reviews(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::apt(gs_plugin_add_search;gs_plugin_refine)
APT: gs_plugin_refine
gespeaker.desktop update 0.8.6-1
qsampler.desktop update 0.3.1-1
frozen-bubble.desktop update 2.212-7build1
kmldonkey.desktop update 4:2.0.5+kde4.3.3-0ubuntu1
org.kde.cantor.desktop update 4:15.08.2-0ubuntu4
texstudio.desktop update 2.10.6+debian-1
ganyremote.desktop update 6.3.3-1
efax-gtk.desktop update 3.2.8-2ubuntu1
cen64-qt.desktop update 20150915-alpha-2
unity-tweak-tool.desktop update 0.0.6ubuntu3
cmst.desktop update 2016.01.28-2
mcrl2-gui.desktop update 201409.0-1ubuntu1
pypar2.desktop update 1.4-7
redshift-gtk.desktop update 1.10-5ubuntu1
GameConqueror.desktop update 0.13-1
YAGF.desktop update 0.9.3.2-1ubuntu1
gigolo.desktop update 0.4.2-1
freedink-dfarc.desktop update 3.12-1build1
smplayer.desktop update 15.11.0~ds0-1
gnome-mpv.desktop update 0.6-1
wammu.desktop update 0.40-1
xarchiver.desktop update 1:0.5.4-2
lyx.desktop update 2.1.4-2
fgo.desktop update 1.5.5-2
kanyremote.desktop update 6.3.5-1
vbaexpress.desktop update 1.2-0ubuntu5
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::epiphany(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::appstream(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x1b04b70~appstream::refine
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::hardcoded-blacklist(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x1b04b70~hardcoded-blacklist
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::icons(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::moduleset(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x1b04b70~GsPlugin::menu-spec-refine(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf vbaexpress.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf kanyremote.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf fgo.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf lyx.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf xarchiver.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf wammu.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf gnome-mpv.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf smplayer.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf freedink-dfarc.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf gigolo.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf YAGF.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf GameConqueror.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf redshift-gtk.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf pypar2.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf mcrl2-gui.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf cmst.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf unity-tweak-tool.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf cen64-qt.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf efax-gtk.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf ganyremote.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf texstudio.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf org.kde.cantor.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf kmldonkey.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf frozen-bubble.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf qsampler.desktop
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf gespeaker.desktop
frozen-bubble.desktop update 2.212-7build1
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::epiphany(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::appstream(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2012990~appstream::refine
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::hardcoded-blacklist(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2012990~hardcoded-blacklist
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::icons(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::moduleset(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2012990~GsPlugin::menu-spec-refine(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf frozen-bubble.desktop
frozen-bubble.desktop update 2.212-7build1
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::epiphany(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::appstream(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x20129e0~appstream::refine
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::hardcoded-blacklist(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x20129e0~hardcoded-blacklist
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::icons(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::moduleset(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x20129e0~GsPlugin::menu-spec-refine(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf frozen-bubble.desktop
frozen-bubble.desktop update 2.212-7build1
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::epiphany(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::appstream(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2007b20~appstream::refine
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::hardcoded-blacklist(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2007b20~hardcoded-blacklist
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::icons(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::moduleset(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): As-DEBUG: run 0x2007b20~GsPlugin::menu-spec-refine(gs_plugin_add_search;gs_plugin_refine)
(gnome-software:4989): Gs-DEBUG: app invalid as no pixbuf frozen-bubble.desktop
(gnome-software:4989): Gs-DEBUG: no search results to show
(gnome-software:4989): Gs-DEBUG: First hourly updates check
I can confirm this bug. app-info/ icons/ubuntu- xenial- universe/ 64x64/, so this app should be shown in GNOME Software.
The pixmap in question is present with the correct name in /var/lib/