Can you detail your display's information (make, model)?
Here are my best suggestions about possible causes and troubleshooting:
1) the source device is not outputting the video in the correct color space (i.e. it is sending the video in the YCbCr color space, while the TV only supports an RGB color space format, or visa versa). This could be caused by the source device's firmware which is not interpreting the display's EDID information correctly, or by the display with an improperly written EDID. To troubleshoot, see if you can plug your source into other HDTVs and/or a DVI PC monitor and see if the problem follows the source. If so, then you can probably focus your attention on the source and contact the manufacturing who might have a firmware update for you.
2) (less likely) the HDMI cable or the HDMI connector on the TV has damaged pins, resulting in some of the color data channels not being transmitted. Try a different cable, or wiggling the cable in the TV (gently! You don't want to damage the TV's connector) to see if this causes the coloration to go away.