A mi me paso algo parecido, por no decir igual, cuando cambie del cable de video compuesto (el RGB creo) en una tele CRT de 21" a mi actual monitor TFT de 24" por HDMI.
En mi caso, solucionarlo fue sencillo, solo tuve que presionar Y + RT cuando arrancaba la consola para reiniciar la configuracion de video y asi la consola pillo la nueva conexion por HDMI y la configuro ella sola a 1080p. Luego puse el nivel de referencia a expandida, pero eso es segun tu tele/monitor.
Desde entonces perfecto y con un definicion brutal, ni siquiera he tenido que andar tocando la configuracion del monitor.