from the release notes in the firmware thread this is a known issue.
Known Issues • It takes a long time (2+ min) to delete song if device has lots of content • There is a pause (less than 1 second) when selecting “Play All” – transition not smooth • Rating info is lost following database refresh on songs loaded in microSD • With Rhapsody channels content, press and hold to add Artist to GoList may not work. Work around is navigate to Album level to add entire albums from one Artist
The delete function is pretty useless because of that freeze. I use the rating system to keep track of what I want to delete, then delete music from the Fuze when its attached to the computer.