I've had to update the BIOS in my [link|http://www.linksys.com/Products/product.asp?grid=33&scid=35&prid=415|BEFW11S4] on two seperate occasions to correct connection problems.
First time was in 2001 to make it work with an iBook. The iBook didn't work at all until the Linksys was updated.
Second time was a couple months ago to work with my dad's new laptop. The laptop connected once, then wouldn't connect anymore - just like what happened to you.