I just found this site, and was so impressed by it I just had to recommend it.
Some of you guys I would guess already know it, for those who don't: midomi.com
Hands off the best song recognition tool I've ever used.
So anyone having some troubles identifying songs with Auto-Tag, definitely, give it a try.
Best of luck,