[Blue Bowtie]

The fact that there is black smoke on startup and that it starts more easily in colder temperatures indicates a rich condition. Your experience is not uncommon. An over-rich mixture can be the result of a failing fuel pressure regulator, leaking injector, faulty TPS, incorrect CTS signal, incorrect MAP signal, or significant vacuum leak.

The EGR valve can cause a significant vacuum leak if it is not closing properly.