My service engine soon light came on and it started doing what the OP described once the cold weather started... However, I only took it on short trips for about two weeks which I think was a factor because I took it today for a two hour drive and it seems to not be stuck in cold weather start mode. Once I check the codes I'll follow up and let you know if it had anything to do with it.
2002 325xi - Titanium Silver - Sold
2009 335i x drive Sedan - Space Gray, M Sport Package