Well, I can tell you about a time I saw something like this, but I am not sure it is related to your situation.
I had serious problems with tasks being unable to find each other shortly after startup, like when they first tried to report back to the namenode. In the end I discovered it was because my mobile broadband connection would sometimes change the hostname of my laptop! And so jobs could no longer resolve the hostname of other jobs. I doubt that's the cause, but, something similar could be happening. Have you set up the conf/*.xml files in the usual way, per Hadoop instructions? so you are definitely telling it localhost is where to find HDFS, etc.?
