I tried it a few times and rate its accuracy at around 70%. Chances are that you'll get your title back in the list of responses. For these screenshots, I help my iPhone up to laptop speakers playing the opening lines of 'John Deere Green' (guitar and drums only, no singing) and Midomi found the result right away (3rd img). From the result screen, you can buy the song on iTunes and search YouTube for related video (4th img).
A fun bonus...when you sing or hum your song, Midomi will let you hear other's singing and humming the same song! (5th img) That's sure to get a laugh. I cracked up when I heard some Asian 'Ob-La-Di, Ob-La-Da'.
If the program didn't crash my iPhone the first time I used it (it's been fine since then) I'd give it 5 stars.
Rating: 4/5
Pro: WOW factor
Pro: Intuitive and simple
Pro: FREE
Con: Crashed my phone on 1st use
Con: Accuracy only about 70%