Well, I have spent way too much time trying to get this printer working, without success.
I have spent hours reading Linuxprinting.org. That has helped some, but not completely. I have tried several ppd files, including the one that came shipped with the 4039 on original diskettes. I have tred configuring the thing through the web interface. I finally spent the time and learned how to configure the thing through the command line.
Just for interest sake, here is the command I used. It adds the printer very nicley.
/usr/sbin/lpadmin -p lex4039p -E -v parallel:/dev/lp0 -m ibm4039.ppd
Note, the ibm4039.ppd file is the one that came with the printer on diskette. I also tried the one called lex4039p.ppd. The printing results are the same with both ppd files. If I print test page from the web tool, it prints a color wheel, ( in black and white) another image of 1 degree radial lines, a box around the outside of the 8 1/2 x 11 in sheet of paper, and the following error message at the bottom.
ERROR: undefined
on command : rectfill
Stack : 158.35 , 36.195 , 216.412 , 255.213 , 158.35 , end_of_stack.
I tried to print through Firefox. It gives a similar result. I was reading the Cups documentation. I did a ctrl + p from the web browser, selected the 4039 and asked for page 1. It printed a 6 inch high C with 1 inch high letters in the middle of the C. (Unix Printing System). I got a horizontal line 3/4 the way down the page, below the graphic. At the bottom I got;
ERROR : undefined
on command : undef
Stack : --dict-- , rowdata , end_of_stack.
Some other things I don't understand. If I try to change the ppd file settings, such as paper size from within Webmin, I get an error reporting the ppd file does not exist. It does, and the path is correct in Webmin. I have looked at the cups.conf file. From what I can see, I should be able to edit this file from my own machine. The default does not allow it from another network printer. You have to edit the file and add an allow + host IP address you want to allow from.
So where do I go from here?

BTW I tried this as a regular user, and as root. Won't work either way.
The Lexmark 4039 10R is a postscript printer from what I can determine. It also supports PCL5. It will print under MDK9.2 if I tell cups it is a HP LaserJet. That doesn't seem to work on MDK 10.1 Official.
I would appreciate any comments or suggestions.