I'm running Kubuntu 10.10 with a Laserjet 5M printer. When I attempt to print a job from Firefox or from Okular, the job never gets onto the print queue. However, I can print test pages on the printer and also print from OpenOffice, so this seems to be app-dependent. I know the jobs aren't being queued because the job number doesn't increase (as shown by the jobs for the test pages). Both Firefox and Ocular give every indication that the print job has been processed correctly.

How can I deal with this?

Are you using CUPS? If so, and if that printer is your default, have you set it as the default printer in CUPS? You should be able to open a terminal and enter
and, viola!, a page pops out.

If the printer is named (and it should be); i.e., you've called it, say, "laserjet" or "LJ5M" or something in the CUPS setup, defining it as the default will make it available system-wide without referring to it by name. It will also be available by the name you gave it if there are more than one printer available on your system but you would print to it with the -d printname option of lp. You set up or manage CUPS by opening a browser and going to http://localhost:631.

Another option is HPLIP (which ought to be on your system by default, if not, install it). That's where you would set up any number of printers, plotters or whatnot and have drop-down menus for choosing which device you want a job printed on. HPLIP is Hewlett-Packard's handy-dandy utility for setting up a printer from scratch (it will create entries for you in CUPS).

Hope this helps some.