Can confirm this.
Connection Speed: 20 Mbit/s
ICMP Ping: 32 ms
HTTP Ping: 56ms
Server Power: 8 Core 4.5 GHz 32 GB RAM
Client Power: 4 Core 2.5 GHz 4GB RAM
Server System: Ubuntu 12.04 LTS OpenJDK & Sun Java, happens with both.
Happens also when they are in the same network (1GB/s, 0.01 ms ICMP Latency, Minecraft around 6-10 seconds for the first time).
Open Multiplayer, wait 20 seconds and then i see a ping ~20000ms
Click 'Reload' and see the minecraft ping going down to ~100ms
Can confirm aswell
On Linux (Ubuntu 12.10 64bit) with IcedTea (OpenJDK) "Direct Connect" works, but "Add Server" doesn't.
The direct connect issue seems to be in Sun Java, the add server one in the Minecraft code.