Check the thermostat. It could be corroded and not closing properly when the engine is cold. If you have not changed it in some time, it might just be worth it to put in a new one.
Did it ever warm up faster? If so, any changes to the engine or engine systems since it ran better?