Spotty High Def on one TV

On our living room TV, we often do not receive the High Def channel option (it gives us the error message "Searching for Signal on Satellite In 1...(771)."  Our upstairs TV gets the high def option fine.  The phone support said it must be the cables, but I have swapped out what I can and no change.  And sometimes we will receive the high def channel, other times not.  Any other ideas?