This problem occurs when using a low quality HDMI cable. I have had the exact same issue. After cahnging the cable with a better one, I was able to get the video.
And for those who want to navigate it the menu:
Press Guide (The big X in the middle) button
2 x Right
3 x Down
3 x A
Now you are in Display Settings menu. Now press down and press A to select a reslution...try and Error method...