Last.fm has a Linux client application, which seems to be a Qt app. It crashes a lot for me. There's also Last-Exit, a standalone Last.fm client for GTK which has a crazy project website.
Now, with Feisty, Rhythmbox itself has Last.fm support integrated. It isn't yet as smooth as Last-Exit, has a few bugs and still lacks some features, but it's usable.
It seems that Rhythmbox is becoming a 'one-stop shop' for all your music-listening needs.