We have observed a dramatic change in the spectrum of the formerly heavily absorbed `overlapping-trough' iron low-ionization broad absorption line (FeLoBAL) quasar FBQS J1408+3054. Over a time span of between 0.6 to 5 rest-frame years, the Mg II trough outflowing at 12,000 km/s decreased in equivalent width by a factor of two and the Fe II troughs at the same velocity disappeared. The most likely explanation for the variability is that a structure in the BAL outflow moved out of our line of sight to the ultraviolet continuum emitting region of the quasar's accretion disk. Given the size of that region, this structure must have a transverse velocity of between 2600 km/s and 22,000 km/s. In the context of a simple outflow model, we show that this BAL structure is located between approximately 5800 and 46,000 Schwarzschild radii from the black hole. That distance corresponds to 1.7 to 14 pc, 11 to 88 times farther from the black hole than the H-beta broad-line region. The high velocities and the parsec-scale distance for at least this one FeLoBAL outflow mean that not all FeLoBAL outflows can be associated with galaxy-scale outflows in ultraluminous infrared galaxies transitioning to unobscured quasars. The change of FBQS J1408+3054 from an FeLoBAL to a LoBAL quasar also means that if (some) FeLoBAL quasars have multiwavelength properties which distinguish them from HiBAL quasars, then some LoBAL quasars will share those properties. Finally, we extend previous work on how multiple-epoch spectroscopy of BAL and non-BAL quasars can be used to constrain the average lifetime of BAL episodes (currently >60 rest-frame years at 90% confidence).