I have two DirecTV HD DVR's connected to a Sony Bravia KDL-52WL140 TV via HDMI cables. The TV has an optical audio connection to a Sony V333ES stereo receiver. The receiver feeds six speakers in a Dolby 5.1 configuration. The receiver recognizes the multi-channel audio from the DVR's through the TV to the receiver, and decodes it properly. Everything there is working perfectly.

I have a Sony RDR-VX535 DVD Recorder that also feeds the TV through an HDMI cable, in the exact same manner as the DVR's. However, there is no dolby digital audio feeding through the TV to the stereo receiver. I know my movie sources are Dolby 5.1. I have gone over and over the setup options in the recorder, but nothing I do helps. I can only get 2-channel audio out of the recorder. The manual makes a point of saying that one should only use a Sony certified HDMI cable. Is it possible that my cable is the problem?

I doubt it's the cable, is there a setup option on the Sony DVDR to enable 5.1 over the HDMI out? I think on my Pannys w/HDMI I had to enable 5.1 over HDMI. Default may have been only over optical audio out.
On Pannys there is a whole setup option dedicated to HDMI configurations, maybe the Sonys are the same?

Yes, I have enabled 5.1 Dolby in the options screen.

I finally came to the conclusion that it had to be the Sony RDR-VX535, so I took it back to Costco and bought a Sony DVP-NS611HP that is just an up-converting DVD player. No record function. That solved the problem. Dolby sound is now working perfectly.