The VLBA was used at 1.6 GHz to observe a target field 50 arcminutes in diameter including the core of M31. Novel VLBI correlation techniques were used to observe 200 sources simultaneously, of which 16 were detected. We classify all 16 as background AGN based on their X-ray properties and arcsecond- and mas-scale morphology. The detected sources were then analyzed for evidence of scatter-broadening due to the ionized ISM of M31. The detection of a compact background source only 0.25 kpc projected distance from M31 places a constraint on the extent of any extreme scattering region associated with center of M31. However, the two sources closest to the core show evidence of scatter broadening consistent with that which would be observed if a compact source were observed through the inner disk of our Galaxy at the inclination of M31. We interpret this as a detection of the ionized ISM of M31 along two lines of sight. With the increases in bandwidth and sensitivity envisaged for future long-baseline interferometers, this should prove to be a remarkably powerful technique for understanding the ionized ISM in external galaxies.