Could this be an entropy problem? Do you have the 'rng-tools' (might be 'rng-utils', I'm not a debian/ubuntu expert) package installed?
I have a vague recollection of blocked reads to /dev/random, which isn't filling quickly enough and stalls processes. /dev/urandom is non-blocking and fills via different means.
Additionally - the issue could in fact not be with your system at all, but with the receiver. If it's only a single host that you have the issue with, I'd be looking at their end.
