I agree with Kurt. After installing hplip, no more problems printing/scanning with my hp 4500. Maybe for some stuff you have to struggle a little with commands, but nothing complicated. In my particular case, I use the hplip-gui to print and command line to scan.

Good luck.