Ugh, OK, I've looked into this and while our last.fm module was technically working, upon closer examination it was very poorly implemented by one of our former contractors and was rather inaccurate.
It *should* have returned correct results for at least a reasonable portion of your media though (it did so for me during testing which is why it originally passed QC), so if not, you probably have a problem with your API key or with your server's ability to communicate with last.fm's servers (eg: a firewall).
That said, I have rewritten the module, reduced it from ~500 complex lines of code to a concise ~30-line routine that is more accurate and much faster, so you'll likely see better results in the next build.
I'll have to examine the iTunes module next as that was written by the same contractor. :/