I take back what I said about HPLIP needing some work. I needed to apt-get hpijs-ppds to get the one for my printer. I guess what I should say is that if they're including HPLIP they ought to include the HP .ppd files for HPLIP or make the "choose a .ppd" thing offer to download more of them.
As Don suggested, there is a bug (#84936) for this. It is marked as Kubuntu-meta, but I'm using Ubuntu, not Kubuntu. It has been rejected for HPLIP and Ubuntu because "well in Ubuntu CUPS does it on the fly so you don't need this." They completely forgot about HPLIP needing it. I hate when bug triagers don't know that one package is used by multiple utilities.