My airport used to be perfect but when Apple did the 10.4.6 update things started to get messed up. I would get the same error that you are experiencing come up a lot and the best way to solve it for me would be to pull my router plug out and start again. This seems to be a lot better for me these days though.
I also used to be able to shut down my computer and restart it without having to apply my WPA settings again but now this is not always the case. I do find having to input my settings when i start up a bit of a pain. I have been on the phone to Apple tech and they said to me that all these issues sound like software problems but even with their attempts to help it didn't put things back to how it was for me.
Under Windows though my Airport is perfect. No matter how many times i log in i never have to input my WPA settings again as Windows remembers it.