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

One of the possible reasons is that your site unable to properly connect to the external world.

Can you please do the following:

1) Re-check if your system basic requirements suffice to run Drupal. To do so log in and visit the page /?q=admin/reports/status on your website. Is there any lines in red color?

2) Enable the 'PHP filter' module. Visit /?q=node/add/page , create a page with any title, Text Format = PHP and the following fragment as content:

<?php var_dump(drupal_http_request('http://updates.drupal.org/release-history/drupal/7.x?version=7.12')); ?>

Save the node, what output you see?

Sorry if #2 is too basic for you - if you're experienced with Drupal you may just install the Devel module and make it in simpler way.

Doing these step can gather useful info for diagnose the case.

OK, so it is a problem with call to stream_socket_client() PHP function which call UNIX C function connect().

If you use SELinux, case #1 described here might be yours http://www.rkrishardy.com/tag/stream_socket_client/ . If it is, this should help you (quoting) :

In a shell console, run as root:

# /usr/sbin/setsebool httpd_can_network_connect=1

Or here http://wiki.apache.org/httpd/13PermissionDenied is a more radical method like turning SELinux off:

setenforce 0

Hope this is your case and methods above helps!

If you're at sharing hosting you most likely not allowed to tune up system. All you can do - is ask hoster are you on SElinux or not.

Another reason (though very non-typical for webhosting) could be is if your installation behind a proxy server.
There are good references to patch for this case.
http://drupal.stackexchange.com/questions/1238/update-status-behind-a-proxy

Good luck!

I encounter that problem by Drupal versions 7.16 to 7.19.

I tracked it down to DHTML-menu so far. Finally it seems to work when setting the weight of the DHTML-menu module to load after all other modules concerning menu functionality.

I've followed your instruction and it returns with this code :
object(stdClass)#48 (2) { ["code"]=> int(-111) ["error"]=> string(18) "Connection refused" }

@myles, most likely PHP configuration of your hosting provider does not allows external connection.

If you have this locally - firewall can be an issue.

See comment#2 from cates111 - this is a success story - initially got an error and now it is working.

I ran into this same issue after installing some new modules in Drupal 7.26 (can't tell exactly which one did it) and played with caching settings in admin/configuration. My core always had the warning on status page about a vulnerability in the /temp directory (https://drupal.org/SA-CORE-2013-003), but I had not found a good post on how to resolve that issue, so I left it. With the sudden failure to detect available updates automatically, I decided to try harder to resolve the temp directory issue. There was no detailed, coherent solution anywhere I could find, but I eventually pieced it together:
1. Navigate to directory root/tmp and delete .htaccess file.
2. Through configuration link in admin menu, go to "File System" section and change "Temporary Directory" from "/tmp" to "tmp"
Problem solved, so far.

Thanks @laak for sharing another success story!

Since we have 2 recipees now in your message and comment #2 I think we can close this issue. (Of course people are welcome to submit more related findings if any)

Old thread but recently had this issue come up on a fairly large site after installing a module. Thanks @Iaak for the tip. I just set a new tmp folder at /admin/config/media/file-system and it seems to be fixed.

Great solution, I ran into the same problem and yes, there was a /tmp/.htaccess file blocking the update checking.
Thank you very much for sharing this.

Thanks #3 worked for me as follow

sudo setsebool -P httpd_can_network_connect 1