The update notifications worked for me in Moodle 2.3.3 but since upgrading to Moodle 2.4, they always fail with some CURL error from here:
http://docs.moodle.org/24/en/error/core_plugin/err_response_curl

In the cron log it states:
"Outdated or missing info about available updates, forced fetching ... FAILED!"

After turning on debugging, the error log has:

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: Default exception handler: Unable to fetch available updates data - unexpected cURL error. Debug: cURL error 60: SSL certificate problem: unable to get local issuer certificate, referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: Error code: err_response_curl, referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: * line 832 of \\lib
pluginlib.php: available_update_checker_exception thrown, referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: * line 718 of \\lib
pluginlib.php: call to available_update_checker->get_response(), referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: * line 481 of \\admin
index.php: call to available_update_checker->fetch(), referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: Default exception handler: Unable to fetch available updates data - unexpected cURL error. Debug: cURL error 60: SSL certificate problem: unable to get local issuer certificate, referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: Error code: err_response_curl, referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: * line 832 of \\lib
pluginlib.php: available_update_checker_exception thrown, referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: * line 718 of \\lib
pluginlib.php: call to available_update_checker->get_response(), referer: http://moodle-address/moodle/admin/

[Fri Jan 04 16:39:45.261608 2013] [fcgid:warn] [pid 2996:tid 6696] [client x.x.x.x:50342] mod_fcgid: stderr: * line 481 of \\admin
index.php: call to available_update_checker->fetch(), referer: http://moodle-address/moodle/admin/