There is a slim chance the power brick is a dud, if you have a spare 12v >1A power adapter give it a go. Most of the WRT54G routers have an onboard power regulator which can tolerate some under voltage (I use to run my WRT54GSv2 at 9v because that was the only PoE splitter I had on hand) however if the adapter can not output the necessary current the onboard system can not compensate.
There was a thread a few months back about how some of the new N type Linksys routers can with weak power adapters that did not supply enough current. Users found greater signal & stability with 3rd party adaptors. It was first posted in the DD-WRT forum and later a thread about it was posted in here.
No, you shouldn't have to do this very often. Once or twice a year isn't unreasonable, but once a month or every two months ? It may be on it's last leg after all...
I found a spare Dlink DI-624 I had laying around seems like the WAN port has better transfer rates but the Dlink settings suck so Im still going to end up with the buffalo and put tomato on it.
So pretty much the Linksys is retired from this point on...