Hi!
Cold might be a slight understatement... We have -20°C and it's the beginning of winter.
For an initerary I can't really help, since I'm one of the people who want to see everything. If you have the chance to head a bit further north, I suggest Amarbayasgalant Monastery, although I don't think there is another way to get there aside from hiring a taxi. In the hostel you'll stay in there should be some tours layed out, maybe you can grab two or three people (if there are any) to take along. Maybe someone else has ideas?
As for Hostels, I've had really fantastic experience with the Golden Gobi and the Lotus Guesthouse. The owners are really nice and friendly and they try hard to make everything perfect for you. Also they look really homely and there has been a lot of love put into the interior. As for prices, the Golden Gobi is cheaper than the Lotus, but I have to admit, the value is pretty much the same (in my eyes. Maybe I'm wrong)
Christmas and New Year: Aside from decoration, there is no impact what so ever. Those are not Mongolian holidays, so they're not celebrated in anyway other than decoration. I'm sure just about everything will be moving normally on Christmas Day and probably New Year as well.
As for the train, I can only tell what I've heard. And that means aside from a long wait and the possibility of having to let the train the searched top to bottom, it should run smothly.
Again, I've never done that, so someone else will have to help a bit more on that one.
As for the expecting part, just expect the unexpected to happen and keep your cool. Getting annoyed is just not worth the hastel and will only make the people not like you. It gets no where.
Have fun
raaawr
