I tried a few really obvious backgrounds (Even a mario background for fun) and found a soft subtle background gave the best effect, although it looks like I went too far. It looked fine on the few screens I demo'd it on, but I'll update with a higher contrast background soon.
Try using something more colorful like a landscape or bokeh so that the perception of parallax feels natural and impactful. I had totally missed the parallax had it not been for the comments here.
I didn't even notice there was a pattern in the background until I read it in a comment here...