I think it's more the consequence of... the brand and model HP All in One. I have not seen it listed at sane.org, I have seen it listed at openprinting.org as paperweight, whereas it is well dectected as a printer and works perfect. It is well detected without any tweaks when connected in USB.
To check your say I should boot a Live KDE4 with pendrive and try to get the scanner to work on the network out of the box.
My own personal install is old but comes from the very first Openbox I had built on Neal's Lxde itself built on a KDE (in 2009). I don't see any reason the flavor would bring or remove anything. And for the packages, having installed task-printing-scanning they
have to be all there.

The only command in the Advanced tab of HP Device Manager is
/usr/bin/xsane -V %SANE_URI%
This is the default. It reverts to this command if I click on the button "default" in the same window. I discovered I could introduce that one (these 2) command line(s) thanks to this:
http://hplipopensource.com/node/211My network connected scanner cannot be seen by OpenOffice or xsane
Applies To
HPLIP Version:
All
Printer(s):
Network connected printers with scan capability
Linux OS Distribution(s):
All
Symptoms:
OpenOffice or xsane cannot see my network connected scanner
Cause:
CUPS queue not configured properly
Solution:
For network scanning, the "hp:/net/..." URI must be configured in the CUPS queue for auto-discovery by OpenOffice and xsane. You can manually specify the URI with xsane using the following format:
xsane <"hpaio" device uri>
For example:
xsane hpaio:/net/PSC_750?ip=12.25.63.142
(Where the CUPS installed device URI is: hp:/net/PSC_750?ip=12.25.63.142, and the hp: was replaced with hpaio:)
‹ I can 'ping' my network printer but 'hp-makeuri' won't generate a device URI for it up Troubleshooting my network attached printer ›
And the only place where I found something looking like what is said above was that one window. I did several tries but not understanding the right way to write the syntax I didn't succeed at once.
There are two entries in the Gimp menu for Xsane ...... one apparently generic one and another which specifies the HP printer/scanner.
Not generic. The upper one is generated by the package xsane-gimp whereas the one below comes from the /usr/bin/xscanimage (I have been told on the #sane chan this afternoon that it is an old outdated program, not giving as many good features as xsane-gimp does. So if you remove the sane-frontends package who it belongs to, the menu below xsane will disappear from Gimp).
Regards,
Mélodie