The appVMs have access to the icons, it's just that they won't consistently show them when I open an application window. And, all appVMs are affected, including those based on Fedora-23.
I know the icons are available because I can seem them next to the program names in krunner. Also, when I initially open an app, a button with the correct icon appears in the Task Manager as the app is loaded, but once it is open the padlock icon usually replaces it. If I use the Application Launcher to open an app, about half the time it actually opens the app without the padlock but with the actual icon (almost always a padlock when I open with krunner). Nevertheless, this is still a big usability issue for me.
A couple other factoids: I also have an Ubuntu HVM. I made two clones of it and, after a few uses, each clone refused to start (invalid filesystem; boots to grub rescue mode and nothing works). Second, I had multiple hard reboots when I first installed Qubes because the hardware only permits a USB keyboard and mouse and they got locked out.
Does anyone have any idea what may be going wrong with the icons? Is it possible that my system is corrupted from all those hard reboots? Any good way to recover from that? Normally, I'd run fsck from the install disk, but not sure that can be done when the disks are all images. I suppose I could also try to reinstall the base dom0 Qubes software and KDE (or switch to XFCE).