Para salir de dudas, simplemente prueba a usar ese cable con otro dispositivo HDMI. Yo probé mi cable con un DVD HDMI que tengo y también me daba fallos de cortes de imagen y sonido, con lo cual me quedó bastante claro que era el cable...
La diferencia con tu caso es que a mi me podía perder la conexión HDMI en cualquier momento, no solo al arrancar la consola.
No me acuerdo de que marca es mi cable. Es de 2 metros, me costo 20 euros en el Corte Inglés y era el que me tenía mejor pinta de los "asequibles". En la sección de HI-FI, tenían cables de hasta 100 euros...
Si no es el cable, entonces es un problema de la TV o de la consola, aúnque me inclino a creer que más probablemente sea la TV. Pero no tiene necesáriamente que ser grave. Igual al arrancar la consola la TV tarda un cierto tiempo en detectarla y enviar la señal que la identifica como un dispositivo HDMI y, en consecuencia, durante ese timepo la consola cree que no tiene ningun dispositivo HDMI conectado y te saca el mensaje. Es que si no es algo así, me parece muy raro que solo ocurra al encender la consola.
Pero, una vez más, solo estoy especulando...