I searched and I didn't see this on here, so forgive me if it already is, but I thought this was pretty damn cool.
Conduits PocketPlayer will scrobble to your last.fm like the desktop media players. I also like the interface, its ipod-touch-esqe
The player is not free, you can download a 30-day free trial here:
http://www.conduits.com/products/player/download.asp
The plug-in for last.fm is here (near the bottom):
http://www.conduits.com/products/player/plugins.asp. It's a zipped dll so just unzip and drop in the install directory.