Ok, so here is the situation. I am also having this error, but my folder structure is as it should be. I have always had the blackberry folder and within it all the media folders(Music, pictures, ringtones etc.). I have both WMA and MP3 files on my phone and have never had a problem. Last week, I recieved a little icon on my BB asking me to upgrade the OS to the new version. Sprint confirmed this was them pushing the new update. I ran the update and since then, I have recieved this error when playing MP3 files. WMAs work with no issues. If I pull the battery and reset the blackberry, my files will play for about 30 minutes or so and then the MP3s begin to get the error again. I tried removing the MP3s and deleting the database file. This did not fix the problem.
Tonight I am planning on wiping the blackberry and then using the BB desktop manager to make sure the OS is properly updated. Unless someone has a better Idea, as nothing else seems to work.