Hello Leon,
This is called banding and believe me, I feel your pain.
There are three ways you could address this problem.
1. Try changing the bit depth in your project to 16bit color (but you have tried that already)
2. If you are using a ramp effect, try increasing the ramp scatter which in effect adds a bit of noise to the gradient.
3. You could also add another gradient under the first and offset a bit, i.e. move it so After Effects has more color to interpret. This brings me back to the first point. 8 bit color has 256 color increments to choose from so adding more data to process could thin out the banding effect.
4. If all else fails, try adding some grain to your gradient and blurring it a little.
These have all helped me in the pase.
Hope this helps.