Spoke for a long time with Aihara-san, good guy.
- Try setting primary and secondary DNS in router.
- Still getting the problem.
- He asked if problem is limited to US sites.
- Confirmed that it also happened on Yahoo! Japan
- He suggested two possibilities: The router is buggy or there is a problem in some remote server somewhere.
- To verify the router I disconnected it and connected my PC directly to the modem.
- Had to add a new Nifty connection in Network Connections of the OS.