How is Haskell better at auto-parallelizing an algorithm compared to say, java's fork/join or .NET's equivalent?
The major difference is that the tools compose with the language better. Instead of having to keep "I'm working in a multicore environment" in your head all the time when you're writing your client code (as you would in Java, worrying about concurrent mutation and so on), Haskell enforces immutability throughout the language. Often you get the extremely convenient situation where you observe that something could be parallelized, change map to pmap and you're now using all your cores.
Compare Guy Steele's talk "Get rid of Cons" at the International Conference on Functional Programming 2009. For the slides go to http://news.ycombinator.com/item?id=814632, the video should also be available online somewhere.
Haskell does keep track of mutations in your program, because you have to wrap those in a monad. Since monads are part of the type system, you are right--but I felt that needed more explanation.
Just to nitpick: Haskell can be interpreted as well, see Hugs. And Python commonly gets compiled to byte-code. (I have no idea how Ruby and Perl implementations work.)
Just last week I asked them what piece of software was missing from their lives in an attempt to get ideas for a new project to start. One of the first things on all their lists was software that would automatically parallelize an algorithm for them. Inwardly I wanted to put palm to face because the easy parallelization in Haskell is one of the killer features I'd been trying to convince them of.
I think the major barrier to adoption is lack of real-world results to show people that's viable. All the benchmarks in the world won't convince these people to change their ways, but if they see other people using it to good effect, they will seriously consider it.