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?

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.