Well while it's not easy to answer a question with virtually no information of what hardware is involved there are a few things to look at.
The first one would be the contacts on the printer where the cartridge contacts these can become dirty and need cleaning a pencil eraser will do that job nicely or an alcohol wipe from a Doctors surgery will suffice if you can not get a eraser in there.
The next thing to do is make sure that the paper thickness adjustments have not been altered as if the printer is set to card and not the usual 80 GSM Paper it would just spit out every sheet of paper so where you load the paper there should be a lever that you can change for the heaver paper or envelopes and the like.
Depending on the make of printer you may be able to update the firmware but as you haven't mentioned the make or model I can not point you to the correct Web Sites for any possible updates and there is always the possibility that the printer isn't compatible with your OS as again you have not specified what it is you are actually using. If you have 9X drivers and are running XP then most likely the drivers for the printer will not work at all so you would need to update the drivers to run with XP. The same thing happens the other way around if you only have XP drivers and are attempting to install the printer to one of the Windows 9X versions it again will not work properly.
Since you said you have bought a new cartridge I'm taking it that you are actually using a Bubble Jet printer and if it is one that has the heads inside the unit and the replacement cartridge only contains ink then the most likely thing to have happened is that the Ink has dried in the Heads and they need cleaning which may not be possible with the maintenance utilities of the printer.
If you would like to provide some more info I'll see what I can do to help you.
Col
