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. – jpmonette Mar 31 '15 at 10:38