I think I have discovered another cause for this. I am having the same issue. I saw several people chalk this up to DNS...however, when I created a simple php script to try and fsockopen my own host over port 80 I see an error 111 Connection refused. Since this is on a server I managed and setup, it suddenly made me remember the firewall I configured. It is VERY common that the very first rule in a firewall is to deny any connections coming over the external card that claim to be originating from yourself. This is a common ip packet spoof used in DOS attacks and why would you be connecting to yourself over the outside network anyway...use loopback. SO, the issue here is that the fsockopen connection over port 80 to myself was being blocked by the firewall. To solve this you need to chnage this line
$cron_url = get_option( 'siteurl' ) . '/wp-cron.php';
$cron_url = 'http://127.0.0.1/wp-cron.php';
You may need to add more before the wp-cron.php if your wp install is in a subfolder. This will cause the connection to be made over the loopback interface and the firewall will allow it as it should.
I suggest (and will create a trac ticket) that the wordpress code change to do this by default, or at least give you the option.