The other great app is shazam id. Test it if you have a s60v3 or s60v5 phone (and it should run on other operating systems, too). It will positively identify 9 tunes out of 10 after taking a 10 secs sample.

Oh how I'd like it on maemo 5! (It's proprietary)