Although you say it has plenty of ink...are you totally sure (sorry to ask) as this sounds like low cartridges to me.
Well, if you know you are going to need more sooner or later you could always go ahead and get them now anyway.
The paper is not the reason. NOT all papers are great, so do seek further professional advice later on re the paper aspect.
A quick thought also; I bough a Lexmark printer for my father-in-law and the cartridge (came with the printer) ran out after no time. Turns out they were half capacity to get you going.
You may have an option on your printer in the Properties to clean the heads. Look under Help maybe?