If still an issue and within the warranty period, drop us an e-mail with your order information.
If outside of warranty, as Nigelar said try a different HDMI cable. Also worth going to Settings and turning off HDMI auto-detection, then trying 720@50, 720@60, 1080@50, 1080@60 (or any of the HD modes offered).
Tried a different TV?
Could also be worth a factory reset if your firmware update didn't involve one.