I'm pretty sure the ECU and temperature gauge are linked i.e. if your (dashboard) temp gauge is reading low, the ECU will think the engine is cold & overfuel.
Flushing / cleaning the coolant pipe is a good idea, but I'm not sure if it will sort it as you will have loosened any gunk around the old sensor when you removed the old one. It's fairly easy, so give it a go anyway - make sure the rubber tubes are clear either end too as I've had lots of stuff collect in these, particularly near the heater valve.
My money's on a faulty sensor and / or connection fault on the sensor. I did exactly the same as you after a rebuild (changed all the sensors) which meant I didn't know which one was causing the problem & took a long time to discover. It did turn out to be the CTS, & not particularly expensive over here (£12)
Have you definitely used the (black) sensor?
http://www.minispare...|Back to search
The other point to note is that the old the MEMS modules can reset to default if disconnected from the battery, so will have to "relearn" the engine's best settings which can take some time.
*Note* do check the 195 deg thermostat is the correct one for Canada spec, as it will not help to have it opening at the wrong temperature. by the way getting cooler when driving "logs show it sees 70C or better until you start driving" suggests the old thermostat might be sticking open.
It took me (and the local mini specialist) several weeks and almost a full a tank of petrol to sort this out, but we did get there - so don't give up!
I do think the temperature gauge is a clue though!!!