KeithPJ, removing the music won't change anything because that's not in the working memory so it's not causing the slowdowns. Instead, try the following:
1. Double-click on your Home button, which brings up the multi-task bar at the bottom of the screen.
2. Touch and hold any one of the backgound app icons. This wil make them all jiggle and acquire a red "delete" icon.
3. Touch the red "delete" icon on all of those apps that you're not using right now, to close them (in the limit, close them all).
4. Click the Home button once to get back to normal operating mode.
In my experience this restores the 3GS to normal speedy operation. Hopefully a future bug fix from Apple will make this annoying procedure unnecessary.
It would be great if you'd report back here that this fix was successful (or not!).