I have a customer who has been fighting with slow/stopped queue processing every time they ran AD Sync, which is on a monthly basis.  Running rebuild indexes on Draft and Published allowed the queue to start processing again, but this article from Brian Smith shows where real problem may be: http://blogs.msdn.com/b/brismith/archive/2012/09/19/when-your-project-server-queue-slows-down.aspx

This is showing promise in the customer test environment and I wanted to share because it's been a thorn in their side.