Update: people are having trouble with this now, I am unable to debug what is wrong, it seems like a problem with mocp.
When not using Amarok (e.g. if I'm low on memory due to using VMs or something), moc is very nice music player (Debian/Ubuntu package 'moc', but command 'mocp'). Here is how to get it to submit tracks to last.fm in a well behaved manner (that doesn't submit tracks if you are just skipping through a playlist):
sudo aptitude install lastfmsubmitd
Add yourself to lastfm group:
sudo adduser [yourusername] lastfm
Download and save my MOC - last.fm script, and make it executable.
Alter your ~/.moc/config to set OnSongChange as per the instructions at the top of the script.
Completely quit moc and restart it.
The advantage of the script I wrote over just using OnSongChange is that my script will wait for half the length of the song before submitting to last.fm. Every 5 seconds it will check you are still listening to that song, and if not, it will quit. This way it will behave much more like Amarok and other well behaved last.fm clients.