I just purchase aHP PhotoSmart C4580  which works well with Linux (you'll still need a windows or MacOS machine to setup the wifi edit: it seems that you can use linux as well with the latest version of the software).

Under ubuntu intrepid (hplip v2.8.7)  only printing works but the scanner seem to be supported by the version 2.8.10  as it's stated in a comment of this post: HPLIP question #45556: “How Do I Configure HP PhotoSmart C4580 Scanner ”

The scanner should be working with the next version of ubuntu jaunty (hplip v2.8.12), but you don't have to wait for upgrade you'll have to follow the installation instructions, and voilà!

I scanned my cell phone to do the test :

Miss Parker