Timeouts that long are usually due to DNS timeouts (or automatic authentication - e.g. "incorrect password" retries in broken Windows Networking implementations like NT4, 95 and 98 used to have timeouts measured in minutes ... I take it you aren't using any remote authentication?)
AFAIAA all the "features" in java where it uses DNS (e.g. automatic unwanted reverse lookups) have by now been classed as bugs and fixed

, so I would suggest it's not a problem within java.
Are you using IPChains (EDIT: or IPtables, same difference

)? If so, what is your ruleset, and have you narrowed down which rule(s) is causing the problem?
Stab in the dark: If you're using the default "security features" there are a large number of things that are being done automatically, some of which are really stupid, and often the distro won't actually tell you what it's done, let alone allow you to pick-n-mix (the linux distros often don't seem to be able to appreciate there's a middle ground between kernel-programmers and 5-year-olds in their user base!). If so, you'll need to run through the list of "helpful" things that are being done. There are all sorts of advanced options by now to do things like artificially delay the initial response to certain ports / packet sigs in order to weaken DoS attacks whilst still allowing legitimate traffic through.