Dual Link is specific for high res monitors. 1920x1080 isn't one, so you shouldn't need that. Also, sometimes Dual Link cables exhibit problems on non-Dual Link compatible video cards.
Does the TV have multiple HDMI ports? If so, have you tried them all just to eliminate the port itself as a point of failure?
Also keep in mind the possibility that the video card is at fault. Unlikely, since you said your VGA out works, but possible for the port's connections to be bad/damaged/blocked.
I agree with rekced, it might be fiscally advantageous to just get a new vid card with HDMI output. Depending on the card you are running now, it might be a very cheap upgrade.