Having just spoken through with printerland support have got it working, but will see if the settings hold for more than a day.
Have had to edit the settings in 5 places, two of which should have been changing the same setting but didn't.
Set the advanced preferences to A4 again elsewhere (Should have worked on step 3 but doesn't):
OK and apply everything. Good luck.
Who knows, but I have never ever seen a printer or driver whereby I've had to change the settings in so many places and what's been set in one location isn't carrying through to the other locations where it is the same setting and should be automatically recognised. Sounded like the support guy was doing back to back calls on these Xerox 6510's for the same issue so something is not right with them. Also the fact it can work fine one day and not the next, for all devices PC, airprint would suggest it is the printer not storing or holding the settings correctly.
Anyway let's hope the settings hold and this works permanently.
That is exactly what was happening for me. I can just say check you've done all those locations, even when it feels like you are doing the same thing twice.
The only other setting I changed was on the printer set the admin > printersettings > duringloading option to no attribute change so it doesn't try and reset itself when the tray is opened and closed.
I have fixed the problem by going into the tray 1 settings on the printer itself and found that tray 1 was set to size "8.5 x 11 letter" so I changed it to A4 and it is working fine now. This is where I went on the printer itself
Admin menu -> Printer settings -> PaperSizeSettings -> Tray 1 -> change it to A4 here
I hope this helps, Also I am on a mac if that also helps others diagnose their issue