Assessing terrain ahead of a robot when repeating previously driven safe paths can be accomplished by looking for geometric changes (e.g., due to the appearance of humans or other obstacles). Previous work has shown that the incorporation of data-driven learning and place-dependence are useful aspects of making terrain classification viable in challenging terrain. This paper presents a learning, place-dependent (LPD) terrain classifier that uses a probabilistic model of the terrain to improve detection of small obstacles in uncluttered terrain while avoiding false positives in more challenging environments. Specifically, a Gaussian mixture model is used to account for multi-height terrain cells that arise in heavily vegetated areas (where both a ground plane and overhanging vegetation can occupy the same cell). A variational Bayesian technique is used to automatically determine the number of components required for each cell using a Dirichlet prior on mixing proportions and a Normal-Inverse-Wishart prior on the means and covariances of the components. The probabilistic nature of the model allows for the detection of much smaller obstacles in regions that exhibit low variance in the terrain surface, whilst still avoiding false positives in regions where the terrain is highly cluttered (e.g., vegetation). The algorithm is tested on almost 10 km of autonomous traverse and is shown to be able to classify a wider range of obstacles than two baseline change-detection algorithms based on absolute geometric differences.