Interestingly the above work-around did not work. I had the matrix switcher (with one input - the DVD-5910A) in between the DVD-5910A and the AVR-5308A. I set and confirmed that the audio setting on the matrix switcher was set to 2-channel PCM audio only (EDID setting #3).
When I then used the DVD-5910A, the matrix switcher and the AVR-5308A, DenonLink performed exactly as before with a random selection of 2 of the 5.1 channels being output through the two front speakers. However, if I set the AVR-5308A to pass the HDMI audio through to the stereo TV (not "amp"), the DenonLink returns to proper 5.1-channel output without touching a 5910A menu. Of course that changes all of the AVR-5308A HDMI inputs, so that isn't a good workaround.
So, for right now I'm back to using the AVR-5803A component video inputs for the DVD-5910A.
Anybody have any idea why the matrix switcher which can modify the EDID didn't work?