Since the TVOS12 update I have had the following issue on my apple TV. Both on the menu and in netflix. Changed HDMI cables, changed HDMI sockets, plugged direct into TV, plugged into soundbar - nothing resolves it.
This is normally caused by issues with the HDMI cable. I know you said you tried another one, but was it the same brand and type? Buy another one to test.