That is perplexing. That printer is listed in my Kubuntu 9.04 on this Wind
Notebook but I can't test it because my HP is a laserjet 1018, which works
fine... some things to consider:

- have you tried rebooting? Cycled power on the printer?
- are you sure of the printer model and double check that it is the model
you have selected in the software installation
- does the printer have any switches for alternate "modes" which might
prevent it working?
- does the printer work on other computers?
- is the data cable firmly attached and does it work with other printers?
- is the port (USB or parallel) able to be used to print to other printers?
And last but not least did you get a good install of Ubuntu? If you haven't
done much with it then consider a fresh install.