One thing I wonder, this is a totally wild guess: Does the scanner itself (on the scanner's own front panel) have some kind of a setting where it chooses to allow certain users to scan, and others not, and do you need to add the freshly-formatted computer to that list of allowed users?
No, not that I know of. I wasn't necessary before (when it did work) anyway, so I don't think it is.
The name "Xerox Workcentre" made me think of this article, which still blows me away. Off-topic from the question you asked, I know, but I'm sure it will fascinate you and the rest of the board as much as it did me:
Xerox Workcentres are Switching Numbers When Scanning.

That, right there, is insanely bad! I'm glad I don't use my scanner for OCR purposes!