I had exactly this problem too on Phaser 6125. The two (6125 and 6130) use the same print engine , just that the 6130 supports Postscript as I recall.
I read on the web that this problem meant that the fuser was not heating up enough to bond the ink to the page. I was heartbroken and thought my old reliable (that I still have and use today , like 9 years now) printer was dying. I had also considered the fact that I had paid 30 USD for a full set of 4 Chinese toner cartridges, but that was not the case as the colors that were doing it the most were GENUINE XEROX TONERS.
It was more noticable after I moved from sea level to the mountains though.
I have no idea what kind of paper you use but as I recall there was a setting in either in the web GUI or the front panel for paper type. I set it for heavier paper and have not had the problem since. I figured if it takes longer to boil water in the mountains the fuser probably needs more heat which I think as you adjust the paper setting it affects the temperature of the fuser. Just a logical guess.
They probably only test these thngs at sea level and in moderate conditions.
By the way, DO NOT GIVE UP on that Xerox.I have been through at least 4 other color Laser printers and this one has outlasted them all. One was a newer Xerox (3XXX series??) that never did work, one was a Samsung that worked for a week then had problems that warranty service did not fix. I traced the problem down to a robboncable on the front panel then a month or so later it stopped feeding paper. Newer printers are JUNK. No other printer will get yo the toner at the price I get the Xerox toner for. No other printer will give you that reliability unless you spend a lot. These things are from the "Golden Age" of color lasers when they were built to last not to be thrown away a year later. Recently I had a problem with an error when I printed. I found out howto get to service menu , reset EVERYTHING and the problem went away. I lost my page count but it is still working and has printed 25000 pages or so , which is more than all of the other 5 or so that I bought over the last few years.
I like these printers so much that I was walking on the street one day and in front of a real estate office were two Xerox Phaser 6125s in their boxes, obviously used, but the guy came out of the office and said they were junking them . WHAT AN IDIOT! I took them home. I am spending less than 20 dollars to have 2 imaging unit chips reset. I already know it will work because I tested with my good printer's imaging chip. There is nothing wrong with the imaging units the counter reached just less than 60000 pages on the chip and shut itself down, on both printers..
