Paper prototypes are highly effective for 3 reasons:
a. Users get a good idea of the future system.
A rough sketch, made of pieces of paper, appeals to users. They get a good image of the future system. Their comments improve the quality of the design.

b. Fast & easy changes.
Users get enthusiastic when they see their comments incorporated quickly. Assume that the very first design is not yet perfect. The designer can make an improved version in just a couple of minutes. Use 3, 4 or 5 iterations to enhance the design, small steps on the road to perfection.

c. Users feel free to comment.
A sketch provokes response (...roughsketches.html). Complicated, technical schema's remain completely out of sight. Users see that the sketch is far from a final design. That removes a psychological threshold. They realise that their opinion effects the design, that the designer has an open mind for their comments.
Sketched prototype The same prototype on a computer screen
The examples show the same design twice. The rough sketch provokes reactions. The computer screen, with exactly the same contents, looks very official. Users have a different attitude to such design. They perceive the design as finished, and are under impression that their opinion is not so relevant any more.

Usually users are fully content with the third till fifth version.

More on prototyping