Cannot SSH/RDP until after pinging URL

Question

If, after starting system (freshly installed Linux Mint 13), I try to run:

ssh mywebsite.com

it hangs up with "Connection timed out". but when I open the browser and enter mywebsite.com there (or even run ping), SSH suddenly starts working.

The same happens with one program accessing it's API through HTTPS. I cannot use it until I access API through the browser. The same happens with RDP protocol. remmina/rdesktop don't work until I ping specific URL.

There are no iptable rules/firewalls on the computer/router. There is only NAT on the router, that's all. Might this be DNS related? What can i do to debug/fix this issue?

Answer 1

Fixed by changing connection type to "Automatic (DHCP) addresses only" and specifying dns servers inside the connection. I suppose issue was with DNS or the router.