I'm not familiar with that router specifically, but there have been various reports from people who have had trouble getting Kindle to recognize especially older model routers. I never had any trouble, either with our old router, nor with the newer netgear we recently got. They've also generally always worked with public wifi.
Things to check: you're entering the correct password: O can look like 0 or o, lower case L for 1, etc. I believe you can also set it so it shows the password as you're typing and keeps it in cleartext so you can check to be sure you got it right before pressing 'connect'.
Cycle the router: unplug it, let it rest a minute, and plug it back in.
Cycle the wireless receiver on the kindle: turn it off, let it rest a minute, and turn it back on. Might also help to 'forget' the network that it's not connecting on and start over.
Go someplace where there's free Wifi and see if the kindle will connect -- to work out if it's a problem in the kindle, which is easily solved by calling Amazon and asking for a replacement.