Looks like it's fixed now? I finally restarted the phone since I left it alone to sync overnight and all the icons seem to be showing up.
I've of course tried the hard reset (holding down power and home button) and it's not helping. Is there anywhere else in the settings that I could reset the index? The suggesting that iOS needs to re-index the icons makes perfect sense. It's just not happening. Also, force quiting and restarting the apps does not help.
This has happened to me since the betas. On my 5s, Mini 2 and now 6s, closing all of the apps in the multi tasking view before restarting the phone fixes the icons.
Fairly certain that while it's been happening for a number of months, it has maybe been about half a year at best, if even that (given that it only showed up around iOS 8.4 and maybe maybe 8.3).Fixed? It's been happening for almost a year!