It wasn't the power. It was a dodgy HDMI cable!
I switched it for a SCART and it solved the problem.
Though if it's an HD box feeding an HD TV by ditching the HDMI you're now watching everything in SD (SCART is SD only)
This sounds like a problem bigger than a dodgy HDMI cable...