That's not really true. Erlang's VM is fantastic at GC with thousands upon thousands of green processes multiplexed onto the system threads, allowing soft realtime performance. Similarly, Haskell's Parallel Strategies library works well with the Parallel GC. Immutability makes this a whole lot easier.
Erlang uses only actors as concurrency mechanism and exploits that fact by giving each actor its own heap. So Erlang's GC does not need to accommodate concurrency, even though Erlang itself does.
To OCaml in particular, and you're right that immutability does make it much easier, but OCaml has mutable variables, which is precisely why it's hard.
Or were you referring to OCaml in particular?