After jumping back and forth between HP's HPOJ and HPLIP drivers, I finally got it to work. All you need is the following packages: HPOJ, HPIJS and the PPD for the PSC 1400 series. Here is how to install it on a Debian box:
apt-get install hpoj hpijs
(this is going to ask you to probe for parallel and usb devices, answer Y to USB and your printer will be detected as "1400 series")
As far as the PPD, it is available here:
http://www.linuxprinting.org/show_printer.cgi?recnum=HP-PSC_1400
(click on Download PPD)
Now you need to place that file in the right directory. In my case (as root):
cp HP-PSC_1400-hpijs.ppd /usr/share/cups/model
and restart cups (as root):
/etc/init.d/cupsys restart
Now, open the CUPS web configuration with your favorite web browser: http://localhost:631
Click on "Printers", then "Add Printer" and enter a name for it (you can skip location and description). If you are lucky, you will have your PSC detected as shown below:

Then select HP as the printer family:

If you have installed your PPD correctly, you should have your PSC 1400 series as an option:

Now complete the installation and print your test page. You will note that it takes FOREVER to print a single page, which I will investigate next. For now, I have accomplished my mission
Update: Printouts in Draft mode (B&W 300dpi) come out at a decent speed.
Update 2:For scanning support all you need is Sane (which most likely is already installed). In case it isn't (or in case you are missing something), issue the following command:
apt-get install libsane libsane-extras sane sane-utils xsane xsane-common
then simply launch The Gimp and you'll see your scanner under File - Acquire