I realized how important storyboard were when I saw David Revoy's amazing work on the Tears of Steel movie. Until then I hadn't realized this was something actually doable, draw the whole movie before doing the 3D. I discovered it is not only perfectly doable, but also incredibly useful.
This is the storyboard we did for a recent work. If you do animations, always do a storyboard before, no matter how good your drawing skills are. The time you'll save later and the understanding between you and your client will raise tremendously. It also serve you as a guide throughout the job, when you were able to build a scene that produces the corresponding image from the storyboard, you can mark it as done, and you have a clear view of your progress.
Also try to do bring most of the discussions at storyboard time, and you'll have very little to change to the scenes structure later on.
This is the complete storyboard:
And this is the content of our "final images" folder. Some sequences changed after the storyboard, but the general shape of the animation stayed the same.
See bigger images here.