I am having this issue where sometimes when I connect my blackberry to my laptop and upload or delete songs, the media player doesn't recognize this.
The "All Songs" list in the media player still shows the old list. What is really frustrating is that many of the uploaded songs can't be accessed. I can fix it by removing the battery and re-inserting, but that's a ridiculous way to have to update your songlist every time you update it... Isn't it?
I was having the same problem and solved it by trying a few different things (like turning off 'Mass Storage Mode' support). The thing I think causes it though is if you have the playlist still active in the BlackBerry Media Player when you delete the files. So maybe just make sure you've cleared any playlists in the Media Player before deleting any files. I hope this works for you.