On a related note, through all this I've installed the DD-WRT firmware in my WRT54G. Though it didn't solve my connectivity problem, it did turn the WRT54G into a full-featured router! (All my other gadgets continues to connect without problems.)

I've decided to get a new router (same brand, and model). I'll update the board about what happens.