From @jonface on November 7, 2014 23:31

Arduino v1.5.8

Problem: The source port for a client TCP connection is fixed to start from 1024. If the micro controller is connect to a NAT gateway, the gateway will store this value. When the micro controller is power cycled (so no connection tear down) and tries to make a connection, once again the source port will be 1024. The NAT gateway will be confused (by the previous connection in it's connection table) and the connection will not start until the source port is incremented.

Fix: In EthernetClient.cpp, function,

int EthernetClient::connect(IPAddress ip, uint16_t port)

Changed the source port so it is set randomly,

randomSeed(analogRead(0));
_srcport = 1024 + random(1, 60000);

I'm sure there are better ways than this, but this connects 'instantly' now however many times I power cycle the controller.

Copied from original issue: arduino/Arduino#2425