If you're using HDMI cables, and assuming that you're using three of them, one for each source and one going to the TV, then I don't know what else the problem could be, unless you have a bad cable (it can happen). With respect to the HD-DVD player, it is possible that there is a "handshake" problem between the HD-A35 and your receiver. Your receiver uses HDMI 1.2 connections, and your HD-A35 uses HDMI 1.3, I believe.
I say that because I had a problem between my 2006 Toshiba HDTV and my 2007/8 HD-A30 Toshiba HD-DVD player, as ridiculous as that sounds. If you see the screen "flashing" between signal and no signal (black screen), then this could be indicative of an HDCP (High-Definition Copy Protection) "handshake" issue. Check and see what happens. One thing that could solve the problem would be a new receiver with the latest HDMI version (e.g., 1.3 or 1.4). My handshake issue stopped as soon as I started running the HDMI connection to my new receiver. Believe me, even the morons at the service centre couldn't figure out what the problem was. I had to figure it out myself.
As you probably don't want to get a whole new receiver, I might recommend that you try hooking up the HD-DVD player to the component inputs. You will still have high-definition playback for HD-DVD's, but you will lose the ability to upscale DVD video. You can then run an optical line for your surround sound. The HTR-6080 doesn't support Dolby True HD or dts-HD Master Audio, so you wouldn't lose much unless you're watching/listening to an HD-DVD that has Dolby True HD, which the HD-A35 would have to process on-board and send through HDMI to your receiver in order for you to hear the "lossless" soundtrack.