Could be a few issues. I'd check the following:
Ensure that your television's calibration isn't input dependent. Some monitors will save different settings for brightness/contrast for different inputs (ie. you could have a 50/50 level for VGA, but blow out the contrast and brightness at 75/75 on the HDMI input).
Check your video card drivers and ensure they're up to date. If you're using nVidia, make sure you've set up the monitor profile to "treat as HDTV" and check any color correction settings (also a good idea to check for overscan).
If those don't work, the problem is in the cable. How long a run is it? Are you connecting it to your graphics card DVI port, or are you using a VGA adapter to hook it to your graphics card VGA port? HDMI and DVI are the same technology (though HDMI is capable of carrying audio as well, and obviously has different termination), so there's no reason that you should experience signal degradation when compared to VGA. It could be a bad cable and you may need a replacement.