I had a similar issue with a cable box and TV. It ended up being the input signal processing board in the TV; any HDMI input would end up looking like that, although sometimes it wasn't right away. I'd definitely check it with another TV before spending money on an Xbox One repair/replace.
I'll check it when I get home tonight. I don't know which to root for, that I have to repair or replace my XBox or my TV. I suppose if it's the TV I can find ways around using HDMI, though after bathing in 1080p gaming glory, going back to low def is going to take some getting used to.
Thanks for the help so far guys!