Soa / parece um problema de fusor, mas se você mudou e não fez diferença, então é meio estranho. :)
Um usuário ou dois no FixYourOwnPrinter.com tem algumas ideias sobre o rastreamento:
Do a half test. Put a sheet of paper on the manual feeder and run a self test from the menu. When the sheet is about 2/3 of the way in, open the top cover to stop the printer. Remove the toner and look at the image below. If it is distorted look at the remaining image on the drum of the toner cartrdige to see if it is distorted. If the image is ok, the fuser is the most likely cause. If the image is distorted and the toner drum is the same, it is most likely the high voltage or laser/scanner optics.