Hi
There aren't too many options for this route, but I travelled to Ulanbataar last February and flew BA to Seoul, then connected to a wide bodied Korean Air flight, which was also an excellent standard.
An alternative I looked at was flying Turkish Airlines via Istanbul and Bishkek, but they used much smaller aircraft like 737's and you wouldn't be able to use your Avios on this route of course.
Hope you find something suitable?