Ok, I can fix this.
It is a problem specific to that one computer. No matter what I do, the printer setup will not keep a simple setting. Every time the computer restarts, it resets itself so it tries to print A4 from tray 1 (when the A4 is actually in tray 2).
The (temporary) solution is this:
1) Print document
2) Wait for print Error to appear on the printer
3) On the printer, Click the "set paper tray" setting (you may need to exit a menu first)
4) Click the tray 2 icon (a4) and hit the green "Go" button on the printer panel
I am working on a more permanent fix (startup scripts etc) which I hope to have done tomorrow.
Dawnsio 'mlaen i'r gwres prynhawn a rwy'n addo erbyn yfori byddai wedi mynd, hwyl fawr i pawb, hwyl fawr i pawb...