The Nuc is connected with HDMI from the NUCs HDMI-1 to my AVR (where I've tried several inputs). The AVR is then connected to my TV and to my projector (since it has dual HDMI outputs). There is no change if I'm just having one thing connected to the AVR.
The AVR is running the latest firmware.
I'm thinking about resolution limitation in the AVR - if the NUC starts with for the AVR an unknown resolution then maybe the AVR gets confused (the AVR also states that the resolution is ???).
Is there any way to force the resolution from the very beggining to something "usual" as 720p or 1080p?
The graphics controller drivers will support just about any video modes (within reason) that the Monitor's EDID (Extended Display Identification Data) claims to support, as well as modes defined within the Video BIOS Table (VBT), plus a basic set of static modes (mostly for monitors with no EDID): 640x480, 800x600, 1024x768, 1280x1024, and 1600x1200.
The AVR may not have EDID as this is not actually a display, its just a device in between. In that case, what could be set is one of the basic resolutions as 800x600, 1024x768, 1280x1024.
720p or 1080p are modes that should be in the EDID of the display to be available through the video options.
The resolution is defined depending on what is detected as connected when the EDID is read.
What happens if you connect another display on the other HDMI port of the NUC and set the resolution to the value you would like on the AVR? You may set them as clone as set the desired video resolution, then disconnect the TV and see what happens after a restart.
I had the same problem with my Yamaha RX-V667, and fixed it by updating the firmware of the AVR. I believe the 667 and 767 share firmware. Check here: http://www.avsforum.com/t/1258247/official-yamaha-rx-v667-rx-v767-thread/3540 for link to 2.11 firmware.