Well, I got the release candidate, and now everything appears to be working! I guess they didn't have the encryption stuff really worked out correctly in the older releases. I'll have to keep up with the firmware (though I'll probably take the "if it aint broke, don't fix it" approach).

In the end, I still wasn't able to use WPA Personal on the Linksys, even though the Airport was in WPA/WPA2 Personal mode. But the Linksys now has completely different encryption options, including WPA2 Personal (it wasn't there before). That one worked.

Thanks for all your help, everyone. I appreciate the assistance greatly.