Comment 3 for bug 109764

Also happening here (feisty, 2.6.20-15-generic). It's not just TCP though, ping is also affected. Haven't tested UDP.
Initial connection attempts to a given host seem to always fail with EAGAIN, and henceforth always succeed until after a certain period of inactivity, which a little experimentation showed to be exactly 900 seconds.

Here's how I measured it:
a=0; while ping -q -c 1 216.239.59.104 >/dev/null; do a=`expr $a + 10`;echo $a;sleep $a;done