I don't know Scala -- but it sounds like a compile-time type-verification problem more than a type erasure problem.

When Haskell targets x86, the x86 opcodes surely don't help Haskell verify that [[Int]] really has [Int]s in there, but it's not necessary because it is proven at compile-time. So I am a bit confused why Scala needs the JVM's help.

Consider that Haskell does its compilation step once; the types and their parameters are discarded and machine code is generated up front. (More correctly, LLVM IR is generated and combined with the Run Time System into a binary.) In Scala, and Java before it, compilation happens during program execution: you cannot discard types because the compilation step is never over. Ordersky's previous work on Pizza ensured that, however, that type parameters _were_ lost; rather than modify the JVM to support generics it proved to be more expedient with regard to backward compatibility just to strip them out. Pre-generics binary code could co-exist with post-generics because they compiled down to the same bytecode. Hence the complaint that in Java Array[Int] and Array[String] generates two special purpose, 'parameterized' Array structures in memory. Mostly the Java compiler can be clever and produce relatively only what is needed during execution, but the PermGem exception happens because, well, it's a hack.

Now, consider the difficulty of Scala wherein it's possible to represent a compound type. Erasure ensures that only the first parameter in the chain is generated in the type-erasure step, destroying the meaning of the union. There are kludgy ways around this--wrapping, bundling up manifests--but in the end the JVM does not allow the transmission of necessary information efficiently. Manifests serve the purpose of maintaining parameter information at runtime, but do so at the expense of code cache space and stress system resources. PermGem exceptions are much more common, in my experience, when doing Scala work as compared to Java.

The shorter answer to your question is the JIT nature of Java combined with a byte-code designed not to maintain the information needed to generate all possibilities of machine code on demand. LLVM IR maintains such information for Haskell--when targeting machine code directly I believe this is achieved by static polymorphic compilation, but I could be wrong; Stack Overflow time?--and the CLR does the same for C# and friends. It's a JVM problem entirely. The JVM promises to perform any and all compilation but is unable to accept all the information needed to do so effectively.