Tried different resistor sizes, still no luck.
This makes me crazy as the schematic is really simple and I see no reason why it should not work. The debounce in this case actually should work so that C1 charges fast in order to generate a clock pulse (clk is posedge) and it really does not matter how fast it discharges as negative edge has no function at all. Of course R4 reduces ripple from the button as it reduces the discharge speed so you would not get posedge triggered by accident.
All in all, this still does not work unless R4 is removed altogether and I can assure you the protoboard is correctly wired. Maybe my 7474s are borked and sink too much current.