At various times, last.fm submissions are refused for various reasons, usually maintenance at last.fm itself. When this occurs, you may notice Amarok giving errors about submitting tracks to last.fm.

To determine whether it's a problem at last.fm, please check this last.fm forum post, especially the "Submissions Server" section.

Thanks to user Scott M. Likens, for reminding me that this should be a sticky!