When I'm using Last.fm for my Motorola Droid, I often have problems with it on regular cell signal. Many times, it will play for a few seconds then freeze and start a new song. I'm in an area with great service so that shouldn't be a problem. I'm actively getting 4-5 bars.
On WiFi, I have no issues though.
I don't have it set to use High Quality so I don't know what the problem is.