Can't Add Printer

I just got an HP D110a Photosmart all in one printer, and I'm having issues installing it, but I'm thinking the problem may be on Apple's end. I've set up countless printers on tons of different computers, network or otherwise, this one is just plugged directly into my laptop because I'm at school, and never had any problems, I'm generally pretty tech savvy, but I'm at a loss here.

When I go to system preferences>Print & Scan> Add printer, i can see it on the list. Then when I go to install it, one of two things happens:

1.) The dialogue will pop up saying it is searching for the required software, but after a minute of searching, it will tell me something along the lines of "Could not find appropriate software using software update"

2.) This seems to happen any time I turn the printer off and then on again before trying. The software dialogue/progress bar will pop up again and start searching, only this time it seems to actually find the software, it downloads it, and it even seems to install almost 100%, but at the very last second, a different dialogue pops up that says it couldn't find the proper software after searching my system, even though I clearly just watched it download and install something to my computer. Pretty annoying since I've tried this several times now, and presumably its possible that I have downloaded the same crap multiple times.

Anyway, normally I don't bother using the disks that come with printers to install them on my own machines because they are filled with a ton of crap that I don't actually need, and I can usually find the basic printer driver somewhere pretty easily. But seemingly out of other options I went ahead and ran the HP install utility to see if it would help. The installation would go all the way through and it would say it was successful, but then if I look in system prefs again, the printer just isn't there, and if I try to print something it doesn't seem to recognize it either.

So basically, the only place OSX seems to recognize that there is even anything there is in the add printer dialogue with the lis of all the printers it sees. Has anybody had a similar problem with ANY printer, or even better this printer that they were able to solve.

I am running Lion, and I suspect that could be somehow related.

Thanks a bunch in advance, I know that was long.

 

I have gone to the website and downloaded the drivers directly.

This printer is on HP's list of printers supported by Lion, I downloaded the HP Lion update.

Thanks for the responses guys. Anybody have any other ideas?