I have the FiOS Actiontec MI424WR router (standard issue) running WEP and I'm having the same problems as the OP. I'm not changing to WPA, though, because then my devices that don't support WPA won't work.
It's ridiculous to expect me to re-configure my entire network for the iPad when my iPod touch, Wii, Xbox 360, PSP, DS Lite, media center, hackintosh Dell netbook, hackintosh custom desktop, and others all connect perfectly.
I'll be waiting (impatiently) for OS 3.2.1.
Although I should say, even with the problem, I'm loving the device itself. I just wish Apple would stop acting like it's fixed because they think it's a dual-band issue. And "switch to WPA" is not a fix.
To those with FiOS: I see Verizon lists a MI424WR-Gen2 router on their site. Does anyone using this version have issues? I'm trying to determine if it's worth the pain and anguish of trying to get Verizon to send me a new one.