Language communities differ in their stock of reference frames (coordinate systems for specifying locations and directions). English typically uses egocentrically-defined axes (e.g., "left-right"), especially when describing small-scale relationships. Other languages such as Tseltal Mayan prefer to use geocentrically-defined axes (e.g., "north-south") and do not use any type of projective body-defined axes. It has been argued that the availability of specific frames of reference in language determines the availability or salience of the corresponding spatial concepts. In four experiments, we explored this hypothesis by testing Tseltal speakers' spatial reasoning skills. Whereas most prior tasks in this domain were open-ended (allowing several correct solutions), the present tasks required a unique solution that favored adopting a frame-of-reference that was either congruent or incongruent with what is habitually lexicalized in the participants' language. In these tasks, Tseltal speakers easily solved the language-incongruent problems, and performance was generally more robust for these than for the language-congruent problems that favored geocentrically-defined coordinates. We suggest that listeners' probabilistic inferences when instruction is open to more than one interpretation account for why there are greater cross-linguistic differences in the solutions to open-ended spatial problems than to less ambiguous ones. (Contains 11 figures.)