Woo!
Right, there's a new package for xmms-scrobbler, I've thrown the URL at Steve McIntyre, so when he gets a chance to review it and upload it, we'll just be waiting for it to get throught NEW again (still from the move between contrib and main). If you're impatient, or the previous version is not working for you, then you can add the following to the end of your /etc/apt/sources.list file and get the new version from there.
deb http://www.sommitrealweird.co.uk/debian/ unstable scrobbler
Hopefully this fixes lots of the bugs from the last version :)