That's a pretty clever circuit but it's a bit naughty. It connects the output of U1D (pin 11) directly onto the green signal output from the VGA card. This could be the reason why it isn't working for you at +5V supply voltage.
I've tried to do some research on VGA signals. It appears that the actual R, G and B signals range from 0V (which is black) to +0.7V (full brightness for that colour). Sync pulses are normally "blacker than black" and this implies that the signal must go negative, i.e. below 0V, during the sync pulses. That circuit will not do this.
That circuit uses a clever method of combining the horizontal and vertical sync, while also automatically detecting the sync polarity. The first three exclusive-OR gates do this. The signal on pin 8 of the 74LS86 is an active-high sync signal, and it's converted into an active-low sync by the fourth gate.
It seems to me that this active-low sync signal needs to be mixed into the green video signal using a method that produces a negative voltage. This can be done using a capacitor and two diodes. If you want to try it, here are the steps.
Disconnect pin 11 from the green video signal.
Get a capacitor of around 10 µF and connect its positive terminal to pin 11.
Connect a 1N914 diode with its anode to the negative terminal of the capacitor and its cathode to the 0V rail.
Connect a second 1N914 diode with its cathode to the negative terminal of the capacitor and its anode to the green video signal.
This may work. If it doesn't, you could try inserting a resistor of around 47 ohms in series with the green video signal connection to pin 2 of the VGA connector.
If these things don't work, we will really need to see some waveforms. If you have an oscilloscope, disconnect pin 11 and look at the waveform on the green output from the VGA card, and also look at the signal on pin 11. Use DC coupling, and take photographs. On the photographs, show where the 0V DC voltage is, and state the number of volts per division, so we can see the maximum and minimum voltages of the video signal. Then post the pictures here. We may be able to figure out what's going on, and recommend a change to that design.