I've tried it on other TVs as well as other consoles on the same TV, so I'm pretty sure the problem is with the genesis itself. I'll try cleaning the connector and see if that helps.
Edit:
Hahaha, I'm a dumb schmuck. Cleaning the connector with some cardboard and alcohol did the trick.