I am having or should say had a simular situation except the Router I had was a WRT54G. It was working fine up until about 3 days ago. Each time I start up the computer, The icon would show that my computer had excellent connection to the router and the cable modem was showing that there were proper signals. But the diagnostic would say that I was connected to the Router but not the internet. The first time, I was able to get things to work by unplugging the power and then plugging it back in. The last time, I had spent over an hour before I finally got connected.
Today, I just got tired of it and now the router is in pieces. The router, unfortunately, was sitting on top of my scanner when I hit it. Yes, the glass on the scanner is shattered too. The Router was under warranty but I needed to be on the internet today not weeks down the pike when a new one would show up via UPS. Rather than spend money to send it back, I just went and bought a new WRT54GS and it seems to be constant so far.