Since I have been quoted, I suppose I should answer. 
bmcs:
My first "real" Arduino project and I stuffed up by ordering a 12v relay module instead of the 5v equivalent.
That presumes the same problem would not happen with the 5 V relay module version. There is no evidence for that.
bmcs:
Is there any change that can be made to this circuit which would stop the relay "chattering" using a single 12v power supply?
Yes, you need a 12V supply that is adequately regulated so that the switching of the relays will not introduce transients into the circuit. If it is a switchmode supply (which it nowadays should be), it needs to have a decent output capacitor.
Given that the power supply is adequate, you need to understand that the "lead dress" - the routing of the power wiring, is absolutely critical.
Power leads must be run as pairs, preferably using some form of "figure eight" wire - that is, two wires with a common insulation - with each ground wire running together with the corresponding supply line. This also applies to the control lines as you neither want the power lines to radiate interference, or the control lines to pick it up.
So with your single power supply, the power to your relay board must be cabled in this manner to the output capacitor on the power supply, and a separate (twin wire) power cabling to the Arduino while another cable of similar form (of however many control pins plus Vcc but not ground is required) goes from the Arduino to the input terminals on the relay board. (The separation of the two Vcc connections on the relay port is detailed in that other post). And there is the concern that using as much as 12 V to supply it, you may have to provide an alternate 5 V regulator to reliably supply sufficient current at 5 V for the Arduino from the 12 V. So the supply grounds only come together at the power supply output terminals, and the control signal grounds only come together at the Arduino board.
There is another matter regarding the relay board and the generation of interference impulses. It is often incorrectly stated that the "kickback" diodes across the relay coils should be mounted close to the relays. This is due to a misunderstanding of the function of these diodes and the nature of the inductive "kickback". Suffice it to say that what is important is that the loop containing the "kickback" diode, the switching transistor and the power supply decoupling be as small as possible as it is in this loop that the switching transient exists.
This means that you should put an additional decoupling capacitor - say a 220 µF and a ceramic 0.1 µF in parallel, across the power input terminals of the relay board to suppress switching transients on the supply wiring to this board.
