This applies to LaserJet 4250 and Color LaserJet 2500
The printer is connected to the network. The IP address must be a static one. To get it one can print out configuration page (choose from the printer's menu, the first page section TCP/IP).
Instead of changing cups, the GNOME will do all the work. Go to System>Administration>Printing. Then choose New Printer>AppSocket/HP JetDirect. Enter the IP of the printer and just click forward all the time. Print out the test page.