UPDATE FROM SALESFORCE
this is due to the fact that there was a performance degradation at salesforce instance on which your sandbox is on, wherein Root Cause was that the problem was caused by inefficient requests which caused resource contention for a node in the database tier. To preserve core functionality for our customers on the instance, action was taken to isolate the inefficient requests, allowing resources to become available. As resources became available, normal performance was restored. So our R&D team has got the performance restored no on this instance.
The link you had mentioned on the case (this StackOverflow ticket), I have gone through that and whenever any one has encountered this slow performance issue, there had been a performance issue at salesforce end.
You can check on our site "http://trust.salesforce.com/trust/status/" to check on performance degradations at salesforce end.
Having the exact same issue in CS17 since the beginning of March. I reached out to the Salesforce support about it, and this is what they responded:
Thanks for your update. I understand you are following the best practice. I am afraid but there is no such process to assign more resources on a single Org. Since it is based on Multitenant architecture and resources are shared among multiple Orgs. We have implemented some methodology to prevent Orgs from monopolizing the shared resources.
Once we execute the test class it will go in queued statue and will start execution once resources are available. You may try deleting old test execution histories and compile all classes to see if it makes any difference.
Please let me know if you have any further query or concern.
I do understand the concept of the multi-tenant infrastructure, but we noticed a drastic unexplainable change in performance in the past month. Tooling API takes forever to process request, while Metadata API is a bit faster.
Going through the UI is also a bit faster to process requests (they must be prioritized over API), but it can take a long time to open the Edit page of an Apex class or Visualforce (sometime ending with the following error).
Time limit exceeded
Your request exceeded the time limit for processing.
Click here to return to the previous page.
Same for unit testing - they are being queued for 4hours, but executed in less than 10-20 seconds.
UPDATE: Here's a screenshot of Status - it seems to be only showing performance degradation for the past 4 days, but it lasted for the past month.

Time Limit Exceedederrors when trying to edit some classes or pages thought. Same for unit test, running them all can take up to 4-5 hours.