Metallic tin powder with diameter less than 50 nm was synthesized by inert gas condensation method and subsequently oxidized to tin oxide ($SnO_2$) along the two heat-treatment routes. The $SnO_2$ powder of single phase with a tetragonal structure was obtained by the heat-treatment route with intermediate annealing step-wise oxidation, whereas the $SnO_2$ powder with mixture of orthorhombic and tetragonal phases was obtained by the heat-treatment route without intermediate annealing (direct oxidation). $SnO_2$ gas sensors fabricated from the nano-phase $SnO_2$ powders were investigated by structural observations as well as measurement of electrical resistance. The $SnO_2$ gas sensors fabricated from the mixed-phase powder exhibited much lower sensitivity against $H_2$ gas than those fabricated from the powder of tetragonal phase. Reduced sensitivity of gas sensors with the new orthorhombic phase was attributed to detrimental effects of phase boundaries between orthorhombic and tetragonal phases and many twin boundaries on the charge mobility.