Are you powering on the TV first, then the AVR, then the video source? Have you tried connecting each source to every HDMI input on the AVR to see if one works better than the current one? Do you have the correct HDMI input on the TV selected?
What's the length of the HDMI cable from the AVR to the TV? Try setting the resolution of the BDP to 720p. If still no joy, you're likely looking at exchanging the unit.