Not all satellite/cable boxes are created equal. Try a little truobleshooting.
Does your box work via HDMI when you connect it directly to the TV? If so, you can always run a toslink/digital coax connection to your receiver to get digital sound.
Then,call your service provider. Tell 'em about your experience with your friends (non-DVR) box. Ask 'em what's up.
With all the different boxes out there they may be your best bet.
FWIW, if you can use component ot may make things a little easier. That can handle up to 1080i if your box can output it. My Motorla cable box can. And, dependig on your TV it may or may not even display 1080i. It may accept it, but it may not display any more than 720.