but that still doesn't answer the question as to why it started happening all of a sudden. The paper hasn't changed.
Perhaps changes in the heat / humidity of your environment. Paper is very malleable and subject to change. All printers have pretty tight tolerances in the paper path.