After chasing this one for a bit, I think I found the answer...
Go to SETTINGS > APPLICATIONS > MANAGE APPLICATIONS
Select the ALL tab
Scroll down to MEDIA STORAGE
Select CLEAR DATA
Your phone will have to rebuild everything it knew about photos and music on your phone, but erased photos should no longer appear as thumbnails or icons and errors in music listing should be resolved!
I decided to create a new thread for this because I had been chasing around different threads for over a month, (most of which ulimately had you reformat the SD card).
I hope this helps!
For what it's worth, I'm using a DROID X.