I see a few posts at fixyourownprinter.com but the fact other PCs do same points to a printer issue.

Try the cheap thing/procedure. Take it to an area you don't mind getting dust. Put on a dust mask and open up the printer, remove toner, etc. and use the canned air on all areas. Put it back together and retest.