This could be a problem with the video codec you're using - many codecs don't handle smooth gradients all that well (perfect gradients don't show up much in real world video). If you render that particular frame as a still image, do you still see the banding?
Try going to the Project Settings dialog and setting the "Noise grain" value to 8 or 16. This will break up the smoothness of the gradients just a bit, tricking the video compressor into doing a better job.
Ya know, I kinda thought that it looked like the codec was being a bit confused by the gradient as well. But I was using the Animation codec. This I was told was uncompressed (is that right?).
Anyways, I followed your suggestion and added a noise grain of 5 to my project settings. That solved it.