Gravitational waves are expected to be radiated by supermassive black hole binaries formed during galaxy mergers. A stochastic superposition of gravitational waves from all such binary systems will modulate the arrival times of pulses from radio pulsars. Using observations of millisecond pulsars obtained with the Parkes radio telescope, we constrain the characteristic amplitude of this background, $A_{rm c,yr}$, to be < $1.0times10^{-15}$ with 95% confidence. This limit excludes predicted ranges for $A_{rm c,yr}$ from current models with 91-99.7% probability. We conclude that binary evolution is either stalled or dramatically accelerated by galactic-center environments, and that higher-cadence and shorter-wavelength observations would result in an increased sensitivity to gravitational waves.