Just a guess.
The original WEP security only supported 64 bit keys. A future enhancement added support for 128 bit WEP keys. What may be happening here is a mismatch between the older BEFW11S4 router (probably using 64 bit WEP keys) and your OS expecting to use 128 bit WEP keys. I’m not sure what that software update was, but it was probably either an update to the router firmware to support 128 bit WEP keys, OR an update to the OS driver to support the older 64 bit WEP keys. Either way, I believe this is likely to be the problem. That’s why hanging on to older hardware (or even an older OS) can be a problem.
Truth is, WEP has been thoroughly discredited as a security solution. It’s easy hacked (anyone w/ interest and even modest computer skills could break it w/ relative ease thanks to tools readily available on the net). Doesn’t matter if its 64 or 128 bit, the protocol is susceptible to hacking regardless of key length. In the end you’re better off w/ a new, modern router that supports WPA/WPA2.
But if you want to get things working w/ what you have, then look in the router and/or PC config for any place where it will let you specify 64 or 128 bit WEP keys and make sure they match. Of course, it’s possible that option is not there. As I said, that’s probably the update the vendor is offering.