How should the paradigm shift associated with functional programming be approached?
Any true paradigm shift requires literally re-wiring the brain. Thinking functionally is not the same as thinking procedurally (for example). The neural pathways of the brain need to be connected appropriately for the new paradigm to become natural. When you were a kid you were, if typical, used to walking and running. Then you probably got a bicycle (or a skateboard if you are young enough). You tried, you fell down, you tried again. Your brain got used to the subtle balancing required. Swimming - same deal. Differentiation - same deal. Haskell - same deal. 

As an instructor, the above implies that you should provide guided practice at the beginning - a skateboard park for the mind. If your students solve a lot of simple problems (not syntactical, but logical) they will skin their knees on these but if they are well chosen will get the skills. In scheme, reversing a list with only head and tail is simple enough. Doing it in linear time takes a bit more skill, but the technique is both cool and satisfying. Writing the code wires the brain. And, like riding a bicycle, it is hard to un-learn it once you get it, since the brain is now different. 

So, make it possible for the students to fall a lot, but to get up without getting discouraged. 

To add a bit of specificity to this. Assuming you know the paradigm well yourself, what are its 100 most important techniques? Can you come up with a 10-30 minute exercise for each of them? Try to have each exercise focus on just one thing (mostly anyway). These are your Etudes. Can you come up with 10 exercises for each of the 100 techniques, even if they vary only slightly? 

Acknowledgement: At SIGCSE 2004, Owen Astrachan (of Duke) convinced Microsoft Research, through Jane Prey, to give every attendee the book The Art of Changing the Brain by James E Zull.