http://reviews.cnet.com/HP_OfficeJet_7410/4507-3181_7-31130701.html?tag=sub lists 802.11g connectivity.

If it's Dead On Arrival (DOA) then pack it up and don't waste your time, but I will mention that many will install firewalls, WEP/WPA, MAC filtering, and stop the SSID broadcasting and then a complaint like yours will occur. Since none of these are stock settings, the HP software may not handle a hardened network.

HP also may charge to support your network.

Bob