Mac OS Setup Assistant: Cannot Print After Changing Zone

After using the AppleTalk control panel to change the zone in which my Macintosh resides, the Macintosh now displays this error when attempting to print to my Desktop Printer:

The document "xx" failed to print on the printer "yy" because the requested printer could not be found. Cancel Job. Stop Queue. Try Again."

Additional observations: the printer does appear in the Chooser but there is no printer icon adjacent to its name.
This error appears when these three conditions are all true:
Some possible workarounds include:

Note regarding the scenario above:
Published Date: Feb 20, 2012