We are running an Ubuntu 12.04 server with the Aegir hosting system and recently upgraded the server software with apt-get. The next day we noticed that the cron queue wasn't running, so we began to investigate. It turns out that the Drush package for Ubuntu had recently been upgraded to Drush 5.9.1, which is incompatible with Aegir 1.x version.
So, after some searching, we downgraded the drush package by searching the apt-cache for the previous version of Drush. Thanks to this post for the idea (http://ubuntuforums.org/showthread.php?t=1033841&p=8695736#post8695736)
sudo apt-cache show drush
From this we determined that the previous version of Drush was 4.5-6. Next, we ran apt-get and specified the version that we wanted (http://askubuntu.com/a/92021).
sudo apt-get install drush=4.5-6
This successfully reverted our Drush version and our queue began working again.