In September 2012, the high-synchrotron-peaked (HSP) blazar Markarian 421 underwent a rapid wideband radio flare, reaching nearly twice the brightest level observed in the centimeter band in over three decades of monitoring. In response to this event we carried out a five epoch centimeter- to millimeter-band multifrequency Very Long Baseline Array (VLBA) campaign to investigate the aftermath of this emission event. Rapid radio variations are unprecedented in this object and are surprising in an HSP BL Lac object. In this flare, the 15 GHz flux density increased with an exponential doubling time of about 9 days, then faded to its prior level at a similar rate. This is comparable with the fastest large-amplitude centimeter-band radio variability observed in any blazar. Similar flux density increases were detected up to millimeter bands. This radio flare followed about two months after a similarly unprecedented GeV gamma-ray flare (reaching a daily E>100 MeV flux of (1.2 +/- 0.7)x10^(-6) ph cm^(-2) s^(-1)) reported by the Fermi Large Area Telescope (LAT) collaboration, with a simultaneous tentative TeV detection by ARGO-YBJ. A cross-correlation analysis of long-term 15 GHz and LAT gamma-ray light curves finds a statistically significant correlation with the radio lagging ~40 days behind, suggesting that the gamma-ray emission originates upstream of the radio emission. Preliminary results from our VLBA observations show brightening in the unresolved core region and no evidence for apparent superluminal motions or substantial flux variations downstream.