We introduce a new Markov Chain Monte Carlo (MCMC) algorithm with parallel tempering for fitting theoretical models of horizon-scale images of black holes to the interferometric data from the Event Horizon Telescope (EHT). The algorithm implements forms of the noise distribution in the data that are accurate for all signal-to-noise ratios. In addition to being trivially parallelizable, the algorithm is optimized for high performance, achieving 1 million MCMC chain steps in under 20 seconds on a single processor. We use synthetic data for the 2017 EHT coverage of M87 that are generated based on analytic as well as General Relativistic Magnetohydrodynamic (GRMHD) model images to explore several potential sources of biases in fitting models to sparse interferometric data. We demonstrate that a very small number of data points that lie near salient features of the interferometric data exert disproportionate influence on the inferred model parameters. We also show that the preferred orientations of the EHT baselines introduce significant biases in the inference of the orientation of the model images. Finally, we discuss strategies that help identify the presence and severity of such biases in realistic applications.