[Summer-16 release notes][1]:

Actually with summer-16 they have improved the cross-namespaced limits.

> but the Limits that are shared across all namespaces, such as the
> limit on maximum CPU time, remain the same. The new cumulative limit
> doesn’t affect these limits.

I don't think there is any direct reason or change which can start causing the CPU timeout exception.Maybe you can provide detail of supporting code sample etc maybe that is helpful 


  [1]: https://releasenotes.docs.salesforce.com/en-us/summer16/release-notes/rn_apex_cross_namespace_limits.htm