Você não precisa reiniciar o roteador, a menos que haja um problema sério de firmware.
Se o seu roteador tiver o DHCP ativado e seu cliente estiver configurado para obter endereços automaticamente via DHCP, execute o seguinte. faça o mesmo que reiniciar o roteador:
Windows:
ipconfig /flushdns
ipconfig /release
ipconfig /renew
Mac OSX Lion:
(Obrigado @slhck)
sudo killall -HUP mDNSResponder
sudo ifconfig en1 down
sudo ifconfig en1 up
Ou na GUI:
System Preferences » Network » Advanced… » TCP/IP