My impression was that those with very little practice programming found Haskell no harder to pick up, if not a bit easier, than those who'd played with imperative languages beforehand -- everyone had a good grasp of high-school algebra (being most of the entrance exam), and that seemed to help more than any programming skills.
I noticed the something similar: people with no previous experience found Scheme much easier to pick up than Java. (Java was, unfortunately, the language in the second CS class.) In fact, as odd as it may seem to people well acquainted with C-like languages, people even had problems with the syntax. Some students just didn't know where to put the curly braces in if statements, for example.
I think starting from Haskell or ML would be similar to starting from Scheme. While I actually like Haskell more for programming, I think Scheme has some slight advantages for learning: there's no syntax, it's very simple and it supports a ton of different paradigms. I would personally like to cover a whole bunch of different paradigms in Scheme before specializing with languages like Haskell or Prolog.
For instance: once the students have a handle on pure code, show them State for, well, state; Maybe/Either for exception handling; Writer for output; lists for prolog-esque non-determinism; ST for a richer model of mutable state; and finally IO for side-effects.
Also, I guess I like "getting them while they're young" when it comes to static typing -- it encourages a certain rigour of thought that I feel serves me well even in dynamically typed langauges.
Seeing someone like that start with Haskell would be pretty cool. There, at the very least, the equations are actually just that.