So when I moved to the (DV) server at MediaTemple, it turns out that my WP-Cron stopped working. I didn’t notice for a while, until I found out that the new version of Tweetbacks didn’t work for me anymore, and this was using wp-cron.
The fix turned out to be very simple, after some debugging with the help of Donncha: in my /etc/hosts file, 127.0.0.1 pointed not only to localhost, but also to yoast.com, and when you opened 127.0.0.1, you didn’t get yoast.com. So I removed yoast.com from that line, and restarted apache, and tadaa! wp-cron started working again.
This might also cause issues for other people, which is why I post about it. It might, for instance, explain why people are having issues with the WP-Super-Cache garbage collection not working.
Let me know in the comments if this helps you, or whether you had to do other things to get it working!