We present an investigation of a partially elastic ball bouncing on a vertically vibrated concave parabolic surface in two dimensions. In particular, we demonstrate that simple vertical motion, wherein the ball bounces periodically at the parabola's vertex, is unstable to horizontal perturbations when the parabolic coefficient defining the surface shape exceeds a critical value. The result is a new periodic solution where the ball bounces laterally over the vertex. As the parabola is further steepened, this new solution also becomes unstable which gives rise to other complex periodic and chaotic bouncing states, all characterized by persistent lateral motion.