On wikipedia it says that the Mongolian People's Republic renamed the city Ulaanbaatar meaning "Red Hero" in 1924. All other post-communist countries seem to have renamed their explicitly communist cities and monuments. Why has the same not happened with Ulaanbaatar?
Ulaanbaatar got its current name in 1924 (formerly Örgöö), so by the time of the fall of communism the name had been there for almost a century. There's also the matter of the city being built mostly from that time onwards, there are very few buildings and areas from the Örgöö era, in a lot of ways its difficult to say they're the same city, since before 1921 the city was mainly a monastery town with some tradeposts.
That said, a lot of stuff in the city was renamed. Districts (then called Raion, a Russian term), which had names like October, Friendship, Worker's, and Partisan, were restructured and renamed by Parliament decree. This can be read here (in Mongolian, though): http://www.legalinfo.mn/law/details/6704?lawid=6704
As far as I've been able to find, no serious attempts have ever been made to rename the city itself, although there have been calls to move the capital to Kharkhorin, site of the ancient Karakorum. Indeed the 1992 Constitution explicitly names Ulaanbaatar as the capital city.