Are the coolant fans behaving themselves?
If your coolant temperature sensors a faulty the fans will be coming on all the time, stopping the engine getting up to temperature.
After replacing both main and inline thermostats, I still had slower heating up - eventually solved with 2 new temp sensors, I now rarely hear the fans running at all.