use your PC and connect your blackberry in Mass Storage mode.
go in the Music folder.
do a search for all files that contain "thumb" il the filename. They may be hidden.
delete all of them.
then, unplug your Blackberry, and go in the media application. Wait for the indexation to finish (there is no indicator of that, but it may take a few hours if you really have a lot of media files.
The search box on top-right of this page is your true friend, and the public Knowledge Base too: