I don't know the distro or the printer. i did once spend a couple hours trying to get an old HP laserwriter to print postscript, which it of course didn't support.
I use red hat and I now have most of the apps printing correctly, but some still misbehave. I did have a similar problem with my system printing seemingly random characters on 1/4 to 1/2 page then spitting it out. Repeatting said behavior until I unplugged it. Think I was sending the wrong format.
Here is a rather coprehensive
*N*X Printing HOW-TO