36,000 seems a bit much to me. As of today, Russia has about 2,600 airports, of which about 600 have a paved runway (source: CIA
world factbook. http://www.cia.gov/cia/publications/factbook/geos/rs.html#Trans
, the Soviet Union was more than Russia, but I can't imagine that adding the CIS states brings the number of airports up to 36,000.
Maybe 36,000 inter-city connections?
Whatever the number, aviation in Russia is a huge thing, with planes going to really far out places (look up, for instance, Plevek on a map and you'll know what I mean), and it's sometimes a bit intransparent for foreigners. But polets.ru is a great source, especially since it lets you look up all the destinations served directly from one given airport. Really cool.