Have exactly the same problem with my Linksys WRT54GS. It lags every minute without fail for between 3 to 45 seconds and yeah online gaming nightmare it is completely unacceptable on first person shooters. Oh and I'm downloading something at the moment, it's going at 25K!!!!!!!! WHAAAAAAAT!!
Don't think it's the age of your router as mines a new g grade and does the same.
I have just wired mine in after spending like 60 quid on the thing. Apparently if your receiving gear isn't Linksys (mines MSI PC54G-BT PCI card with latest drivers) the Linksys wireless routers won't communicate to well with it. I was recommended to get a Linksys dongle or card and told that should solve the problems but personally I won't be touching anything Linksys again, I don't like their tactics.
Anyone got any ideas that avoid spending more money would be greatly appreciated