O Last.fm é um registro de tudo que eu escuto. Daqui a vários anos vou olhar lá e dizer qual foi o artista que eu mais ouvi durante toda vida.
O problema do Audioscrobbler, tecnologia que faz tudo isso funcionar, é que ele só tinha clients para o PC e alguns outros dispositivos, como o iPod que faz sincronização offline com o aplicativo Last.fm.
Tenho um Nokia N73 e sentia muito falta de poder sincronizar minhas músicas para minha lista online.
O meu maior tempo ouvindo música é no celular, então, tudo o que estava gravado no Last.fm era um reflexo das poucas horas que escuto música no computador.
Procurei algumas aplicações, e tive que garimpar muito para achar algo razoavelmente bom para o celular. Basicamente se destacam essas duas apps:

• ASPY Player
  

Prós: O primeiro scrobbler do Last.fm para os celulares Nokia Serie 60. Toca em um player separado, diminuindo a quantidade de aplicativos rodando ao mesmo tempo.
Contra: Instalação avançada e interface dos comandos do player com pouca usabilidade

• Mobbler

Prós: Se integra com o player nativo do seu Nokia
Contra: Roda em segundo plano durante a execução, ou seja, dois aplicativos

Ambos são bons aplicativos, freeware (grátis), e fazem, muito bem o serviço. Você pode ouvir suas músicas e depois sincronizá-las todas de uma vez, diminuindo o seu custo com dados. O envio das faixas é feito em poucos segundos podendo variar de acordo com a quantidade de músicas que você escuta.

Qualquer dúvida, é só me perguntar.