I'm not familiar with HDMI technology as of yet, so I am going to take a wild stab in the dark.
From what I understand previous generations of HDMI cables may or may not have been verified for full HDMI 1080P pass through, although they were marketed to the consumer as fully functional... perhaps someone who is familiar with HDMI tech can enlighten us if any old spec cables limited audio transmission in any way
How old are your cables? I only ask because they are the one item you didn't include on your list of gear.
Edit: on a second read through you seem to be confident that it's just the receiver that will not cooperate. I'm sorry, I know nothing of yamaha receivers, but good luck. I hope someone can help.