So did turning off bi-directional support fix the problem? That seems to be the only suggestion in the link.
YES! It seems too easy. But it worked.
To find this, I just typed the junk characters I was getting into Google: s1M.
Nothing else. This article is at the top of the results.
The article starts: "I have a HPLaserJet4P and I had to buy a parallel to usb vs. a parallel to parallel cable to hook it up to my new Dell computer and now everytime I print it prints the job but wastes an additional blank page with just s1M at the top left corner."
That was the same cable type, printer model, and junk characters I was getting.