Definitely sounds like a bad T-stat. BMW's get warm pretty quick (as you mentioned based on previous experience) and the only time I've had it take more than 10 min or so while driving was around -40 F.