You may have an old router that doesn't support WPA. You should go to the router manufacturers website and see if you can get a firmware upgrade for the router to allow it to do WPA.
Your Airport entry in System Preferences > Network might be screwed up. Here is a suggestion. Go into System Preferences > Network then click the Location: drop down, click Edit Locations... and highlight the name of the location you use for Airport then click Delete. Then shutdown and restart MacOS X. Go back through the same menus, but this time choose New Location... and create a new one. Then, make sure this location shows in the Network window. Underneath Location: you will see the Show: drop down box. In here, choose Network Port Configurations and in the box below, make sure Airport is checked AND drag Airport to the top of the list so it is the first one there. Next, change Show: to say Airport and under By default, join: make sure it says Preferred networks and make sure your network is the only one in the list and that it is on the top.
After doing this, setup WEP or WPA/WPA2 and hopefully it will connect automatically on startup.