Have you tried using Google's web master control panel. They have a link checker tool. I have always been wary of using external tools to run queries on Google as they sometimes frown upon it. On another note it is quite possible that the service is being temporarily updated.
Google Webmaster Tools has the most reliable backlink checker you can use. Click on the 'Links' link at the left side then select 'Pages with external links Help'. Don't use the 'link:' function in the search box either, that's not accurate. I also think this is a good tool to use... http://www.iwebtool.com/backlink_checker
have you tried searching for your solution ?? use yahoo to check your public links, and webmaster tools to check your google links..