A search is reported for the pair production of a new quark, b', with at least one b' decaying to a Z boson and a bottom quark. The data, corresponding to 2.0 fb^-1 of integrated luminosity, were collected from pp collisions at sqrt(s) = 7 TeV with the ATLAS detector at the CERN Large Hadron Collider. Using events with a b-tagged jet and a Z boson reconstructed from opposite-charge electrons, the mass distribution of large transverse momentum b' candidates is tested for an enhancement. No evidence for a b' signal is detected in the observed mass distribution, resulting in the exclusion at 95% confidence level of b' quarks with masses m_{b'} < 400 GeV that decay entirely via b' to Z+b. In the case of a vector-like singlet b' mixing solely with the third Standard Model generation, masses m_{b'} < 358 GeV are excluded.