"There was a problem checking available updates for Drupal ..."

I have recently installed Drupal 7 for a new site I built and I can't get it to update. When I go into the administration pages, I get messages saying that:

"There was a problem checking available updates for Drupal ..."

When I try to "Check manually" it gives me an error that it failed to retrieve updates for (any number) of modules. My initial installation was 7.9, but I have since switched it to 7.12 and have had the same problem regardless of what modules are installed. This has happened since I had only core installed.

I have checked and checked and no one seems to have any kind of solution for this problem.