Depending on how old the printer is it's possible that it doesn't support all types of wireless security. I changed the WPA type on my router once and the nintendo Wii wasn't compatible, so I had to change it back. There seems to be a lot of confusion here, and I myself am not really sure what the trouble is, but these are the steps that I would follow.
1) Consult the printer manual and figure out exactly what kind of wireless security the printer supports.
2) Armed with this information, log into the router and set the wireless security to that same type.
3) When you set up the wireless security mode you'll enter a passphrase or generate one depending on the type of security, this is what should be entered into the printer in order for it to connect.
4) If the printer won't take it then you should verify connectivity on another device. Can other computers and devices connect to the wireless network? If so then it's the printer, if not then something isn't set up right.
I hope this was helpful.