Here is little effort to share what I know about these issues:
Have you seen this in your environment as well?
Yes, In various Salesforce environment I have seen this issue. This
issue is not limited to Developer or Production instances. We have
seen this in full sandbox instances. Instances in which it has been
identified are na26, na2, na23 and cs10. There chances that it occur
in other instances but all are North American Instances. In addition
to CPU limit, SOQL Time out error has been seen on code which was
running fine for few years. Same issue has been posted in Salesforce
Why does it happen?
This issue started occurring right before release of Lightning
Experience and Winter '16. There is no official note about this error
but it is being fixed in several instances. This issue occurs in
random time frame. So you may get your test classes passed in some
time slot during a day.
Is there anything we or Salesforce.com can do against it?
Case can be logged. But their is no official note about it. This will
be fixed eventually. We had it in few sandboxes, now they are working
fine without any code modification.