I suspect the Belkin router you're using also supports WPA. Unless you have other devices that do not support WPA on your network, I suggest selecting WPA over WEP. However, as you indicated, anything is mostly better than nothing at all.
As the other post indicates, you'll need to consult the documentation on the Belkin router. The documentation with Belkin products is pretty sound, so it shouldn't be much of a problem.
If I recall Belkin routers, log into the router with a web browser, select Wireless Network and you'll select the encryption. Your options will be WEP, WPA-radius and WPA-PSK. If you select WPA, you'll want to use WPA-PSK. Enter in the password in the box and save your settings.
Next, stop your Airport, reconnect to the network, give it the magic password you just created and it should work without a flaw.