Printer won't connect wirelessly to Mac Book Pro

I'm helping a friend set up her new wireless printer to interface with her Mac Book Pro running OSX10.7.4. She has a HP Photosmart 5510 and the router is a linksys, not sure of the model but fairly new. When we installed the printer it installed with no problems to her Dell desktop & Acer minicomputer & prints fine wirelessly. The software installs on her Mac (I used the latest version with the up-to-date drivers from the HP site) but will not print...gives a 'device not found' message. She can print using USB but the point of the new printer was to do it wirelessly.

The Mac is connected to the router and works wirelessly for other functions. I printed a test page for router and everything passed. The printer is working wirelessly also. Something is preventing the Mac from talking to the printer. I followed the suggestions on the HP troubleshooting site but nothing works. The site did have a critical update for Lion users which I tried to download but kept getting a 'disk is full' message. This is a fairly new computer that had standard Mac software plus MS Office. It's used primarily for documents in a work environment...so no games taking up space. Not sure why this won't download but if it did maybe it would solve the problem. Otherwise, somewhere along the way Bonjour was mentioned as a possible issue. If this could be a problem, is there a resolution?

Any suggestions would be greatly appreciated!!

I installed the software and at the beginning of setup it asked if I wanted to connect wirelessly. I checked the box for yes. It instructed me to connect with a USB to do that. I did, it transferred the settings from the printer (I assume) and told me to disconnect the USB now. I did that and it finished the setup. However, when I try to print I only get a 'device not found' window.

Sorry but no good news as I never found a solution to the wireless printing problem. The printer works wirelessly with the windows computers but not with the mac. It prints fine with the mac when you connect the USB. My friend likes the printer and is willing to put up with the inconvenience.

I have a HP Officejet 6500 wireless and it works fine with my mac desktop. My daughter-in-law visited with her mac laptop and was able to print wirelessly once she installed the software. Maybe certain models do better than others?? I think we should be making big noise to HP to get this fixed...must cost business because there are a fair number of mac users.