Yeah that is one of the huge issues that came with the last update. It might not happen to everyone, but there are a ton of people with that problem. As far as I know, that is suppose to be one of the issues that will be addressed in the next software update which still has no specified arrival time.
Until then, if you want, you can use a 3rd party music player from the Market. I used MixZing for a while, which was pretty decent. A new one came out recently called PowerAmp, and it is very nice. I got rid of MixZing and have been using that. It's unfortunate that I have to result to downloading 3rd party apps to get my phone to work right (though PowerAmp is much better than the stock music player app anyways), but the stock music player just freezes my phone. You can try deleting the 'data' for the music app and/or doing a reboot/battery pull/ factory reset, but for me, nothing worked. If one of those fixed the problem, it would always come back in a few days and freeze again.
I actually noticed more problems in other areas of my phone after using the stock music player app. What I did was a factory reset, and NEVER opened the stock music player app again, and then just downloaded a different player from the market and it has been pretty much smooth sailing since then.
I wish you luck.
