Have you got it set up for HDTV in the display settings on the System blade - that should sort you out.
If not, then double check all connections - if it's the cable that came with the 360 with the red, green and blue plugs, then it isn't an HDMI cable, it's just a hi-def cable, with a switch on the side to choose if you want standard or hi-def output, just as a heads up. The HDMI cable won't fit into a standard 360 unless you have an Elite.
If you've double checked all connections and the System blade, then see if you can try the cable with another 360.