maybe something wrong with the fuel heater on the filter? When was the last time you changed your fuel filter? IMO that is too long to go for filter changes. Last one I changed was at about 9000 miles or anout 14400kms and it was almost all the way used up. (really black) I change mine with every oil change...it is cheap insurance. Also, possibly your glow plugs or controller for them may be going. It is strange that you would have a problem at a small temp range though. Does it still do it when you plug in the block heater?