You are indeed right about shades of grey. You're encoding in 8-bit 4:2:0 (standard h.264 settings) which means that there are only 256 possible shades of grey. Think about it. If your RGB* values go from [0, 0, 0] to [255, 255, 255] and the red green and blue channels are equal, because grey, then your pixels will be one of these values: [0,0,0], [1,1,1], [2,2,2]… [255,255,255]. Meaning 256 possible colours.
If your gradient went from full black to full white and was 256 pixels across there would be one pixel per colour, so you'd be fine. But if it was say, 1024px wide, then there would have to be four pixels of each colour next to each other, meaning bands. And that's a gradient going from full black to full white—a subtle gradient from 45% grey to 55% grey might only have 25 possible values available–it's going to be banding city.
And just to explain what is going on in your image–especially in the middle–there's an unfortunate optical illusion that makes those bands super obvious, by making the squares where the same colour is repeated look like gradients going the opposite way.
Two possible workarounds:
You can encode using 10 bit h.264, but a lot fewer people will be able to play it back, and you'll need to get a 10 bit build of ffmpeg or x.264 (I don't know of any other 10-bit h.264 software)
You can add some noise. Sounds crazy, but it will break up the bands into fuzz so they'll be less noticeable. Justify it to yourself by believing it gives it a more filmy look. It's called dithering, it was a big thing back in the days of 8-bit colour.
*Actually it's YUV, but that's not important right now.