Russell, I had a similar problem. Do you have more than 1 cable box in your house? I have 2, and when I got the HD box, they sent the signal to the other box. I kept calling tech support, they would mess with something on their end, tell me to leave it off for 5 minutes, then turn it on, if it doesn't work, call back again.
Finally on the 4th call I got someone who actually sounded intelligent right from the beginning. Within about 15 seconds he said "Oh sorry, they were sending the signal to your other box, try it now" and it worked.
The money pit:
$3800 spent sofar :p