I have a personal domain on google apps. The login ID is different than the email address I use/advertise.
e.g. my username for login is first-initial+last-name@[domain].com
But the email address I use for everything on that account is first-name@[domain].com
This service states that my account was compromised on 12/12/2010 most recently at the first-name@[domain].com though you could not login to my account with that email address...
So - how valid is such a check. Also - without it showing what information it is checking against, it feels really spammy. as if they are asking you to enter your email for a "check" knowing that you will enter a valid email - then they harvest the email as valid for spam.
To me this means that my password is out there, and now a part of someone's dictionary. Change all places where that password is used immediately. I am currently moving to LastPass with randomly generated 16-32 char passwords for every site. It's less of a pain than one might think.
It says it's using the perlmonks.org database, and I _know_ my password was revealed there (thanks to me foolishly reusing it on twitter), but it's not showing that against my email address...
It should tell you which sites were compromised such that you can ID if you used your email at any of said sites.
Just saying ambiguously that there was a site which may have been compromised out of the 2 billion sites online is laughable.
In fact, I would say that prompting the average person to change some passwords either way, is a good thing.