Clio DCi rough idle when cold

This is not an intermittent problem - it happens everytime the car is cold (first thing in the morning or after standing for 5 hours at work).

First happened once the weather turned colder (below 8*c back at the end of October '11)... once the car is warm - starts and runs with no problems.

The Problem/Symptoms: Rough Cold Idle

All lights on the dash as normal on ignition
All lights off on the dash as normal after ignition.
Turns over on the starter fine.
Fires up within 1 second
Immediately stalls.
2nd start (as before) but engine will fire and run - but will be rough - idling at low revs (occasionally engine 'bouncing' for a second or 2)
(If I do 2 -3 preheats before firing the engine, it will fire first time and idle slightly better)

Normally within 1 minute of the rough idle phase, the revs will increase to the proper rpm and the engine will purr quietly. After this it will run perfectly normally... until the next cold start.

Things we've already tried:
TDC sensor: cleaned (had a warm start prob back in Aug)
EGR Valve : cleaned (including the large pipe next to the valve - very clogged with carbon)
New Battery (1 week ago)
New Glow plugs (1 week ago)

Tomorrow we will be trying the fuel primer bulb before starting.. see if that helps.
Other than that, wondering if it could be a coolant temperature sensor that is giving the wrong info to the ECU.

Any further suggestions will be most welcome.

Thanks in advance :)