I have reseted my WRT54G router, just to realize I have lost all Internet connectivity.
Basic Debug showed that the router can access and ping the gateway, and then Internet, while PCs behind it cannot.
Changed a few setting, disabled uPnP support, saved… and it started to work again.
I have no IDEA what caused the problem, but now is not a good time to investigate further.