I know this thread is two years old now, but I may have found something that could apply to you.
The problem I encountered was similar but not exactly the same: I lost my personalized ringtones and tones. They were still there on the phone, Music player would not find them. In fact Music Player would crash, after NOT finding the few songs I had uploaded ages ago. I will not describe all the other symptoms, but the Gallery: it was not showing any pictures at ALL (not the ones taken with the camera, or the downloaded ones or, etc.). Gallery would not crash though.
I tried many things, including the suggestions in this thread and a couple others. My phone service provider would not suggest more than what I did already, redirected me to Samsung. They in turn recommended to reset the phone to factory settings (losing all my data, apps and customisation, hence a few days of nightmare). This reminds me how the smart guys at Microsoft support repetitively suggests your reinstall your PC as it was 3 years ago before considering helping you.
So I gave up for a few days, mourning about the crazyness of these closed systems (I don't want to lose time rooting the thing).
Then... I search for the commonality between Gallery and Music Player. The answer is ".nomedia" file, which (thanks Ethan who wrote about the topic elsewhere [I may not post the link]): "In Android, a .nomedia file is basically a BLANK file with “.nomedia” as the file name. You can place this file into a folder to inform the media scanner that any media files inside this folder should not be shown in apps such as Gallery, Video and Music Players."
Tada! There was a .nomedia file at the root of my directories, preventing the phone to be scanned. Removing it did it!
Gil