Have you used the HPLIP drivers or the ones which came with Ubuntu. If you're using the standard ones,then change to the HPLIP drivers. You can get them from hpinkjet.sourceforge.net