We report on an observation of the Broad Absorption Line (BAL) quasar PG 1115+080 performed with the XMM-Newton observatory. Spectral analysis reveals the second case of a relativistic X-ray absorbing outflow in a BAL quasar. The first case was revealed in a recent observation of APM 08279+5255 with the Chandra X-ray Observatory. The spectrum of PG1115+080 indicates the presence of complex low-energy absorption in the 0.2-0.6 keV observed energy band and high-energy absorption in the 2-5 keV observed energy band. The high-energy absorption is best modeled by two Gaussian absorption lines with rest-frame energies of 7.4 keV and 9.5 keV. Assuming that these two lines are produced by resonant absorption due to Fe xxv Kalpha, we infer that the X-ray absorbers are outflowing with velocities of ~0.10c and ~0.34c, respectively. We have detected significant variability of the energies and widths of the X-ray BALs in PG 1115+080 and APM 08279+5255 over timescales of 19 and 1.8 weeks (proper-time), respectively. The BAL variability observed from APM 08279+5255 supports our earlier conclusion that these absorbers are most likely launched at relatively small radii of ~ 10^(16)(M_BH/M_8)^(1/2)cm. A comparison of the ionization properties and column densities of the low-energy and high-energy absorbers indicates that these absorbers are likely distinct; however, higher spectral resolution is needed to confirm this result. Finally, we comment on prospects for constraining the kinematic and ionization properties of these X-ray BALs with the next generation of X-ray observatories.