I know this is not an answer but I don't have enough rep to comment
We have experienced this in 2 of our CI ORGs which are mapped to 2 different code bases (one of them hasn't changed in about a month).
From what I can see the CPU time limit seems to be coming from the Salesforce String/Matcher classes.
Just wanted to give you what I have seen so far, maybe it can spark an idea from somebody out there who can give a hand.
UPDATE: Finally heard back from Salesforce that they pushed a patch to the Spring '16 update. The issue was around the handler for the Apex Logs on the Salesforce side that was using a large amount of the heap.
As of yesterday, they have rolled back that change and now things appear to be working for me.