Long place and route after adding logic lock regions

If you can submit the design, please file a service request at altera.com. That does not sound right, or at least it sounds like something Altera should fix. As sw181 said, I'd be curious if it's in placement or routing, and though it's possible, I'd be surprised if it's directly either. Some other thoughts are that it could be physical synthesis(a portion of placement), as perhaps the re-synthesis algorithm mistakenly loops into an algorithm too deep. Another thought is that the timing analysis takes too long. How long does your TAN/TimeQuest process run at the end? Note that during placement the timing engine is called many, many times to analyze it's current placement. It's a condensed call(i.e. each one is much shorter than the final call), but if some timing analysis loop blew up, that could explain it too.