I was reviewing the documentation on that printer, specifically the Network Guide, and noticed two things; the printer dates back to 2004, and it only mentions WEP/WPA (not WPA2).
http://h10032.www1.hp.com/ctg/Manual/c00389927.pdf
That raises the very likely possibility that the printer is expecting WEP/WPA, but your new router is configured for WPA2. If that's true, then you have to either use a wired network connection, or else use WPA on the router. Some routers will have an option that supports both at the same time, so that might be a solution as well.
P.S. I checked that guide a little more closely and found this (pg., 36):
Types notsupported include: WPA2-AES, WPA2-TKIP, LEAP, PEAP, EAP-MD5, EAP-TLS, or EAP-TTLS.