I've made some serious progress now :P
I went to the store and bought all the cables needed for testing (usb to serial, serial, coaxial, optical) and then I tried all of them.
I didn't succeed with upgrading the unit, I couldn't make any contact with the AVR through the serial cable, even though I had the drivers for the usb adapter installed and it was listed in the device manager.
I also tried on an older computer with an actual serial port, but it was running Win98 (not supported according to the min req. for the upgrade program, though the program started) and I couldn't make any contact there either.
Then I tried the optical, and guess what, it worked!

I was able to get some great surround sound out of my HTPC.
Then I tried the coaxial, and that worked too (not surprised since the old owner had it connected that way).
I also tried the 5CH stereo mode again, and now it worked too

I don't know how, but I am at least glad it worked.
I have also tried with a shorter hdmi cable (moved the receiver) that is 2m, and that didn't work. So the cable length is not a problem.
So yeah, the only thing I haven't really tried now is the "monitor output" (3xRCA). But I am pretty sure that works, and I'll maybe test it later with some old ****** little fat tv.
My conclusion off all the testing is:
The HDMI system is broken, and could possibly be fixed by updating the system. But since I couldn't make any contact with the receiver through the serial port, there's a possibility the serial port is broken too (though very unlikely).
I could just leave it like this and run the audio via the optical cable, and the HDMI straight to the projector (since I'll probably only have my HTPC connected anyway). Cons? I'll have a defunct receiver which will be harder to sell later on (lol I bought if for aprox 250$ so maybe there's no value in it in like 4 years).
I am thinking about going to the hifi-store and let them take a look at it anyway, and maybe fix the hdmi issues for a small cost.