For prototypes I'd say that you need to get to the level of detail where you are able to explain and illustrate the functionality in a way that is easy to understand.
However, it is also of major importance that no-one believes your prototype to be a finished (or nearly finished) product. In that case you run the risk that your customer either thinks that you can deliver tomorrow ... or you'll find yourself stuck in a discussion over minor (cosmetic) details—in a prototype that is not necessarily meant to look exactly like the final product, that is!
In general, an unfinished / unpolished prototype or mock-up will invite user input, critique, and alternative solutions. It can make users see potential transformations of existing practice (Ehn & Kyng 1991, p. 652). Also, it will hardly be mistaken for a final product (Ibid.; Beyer & Holtzblatt 1998, pp. 372-3). (This is precisely why I love Balsamiq Mockups.)
A functional prototype, on the other hand, makes it possible for users to get hands-on experience in concrete usage situations (Bødker & Grønbæk 1991, p. 198).
In a prototype there is no question of an attempt at completeness; its function is to throw light on specific aspects of the information system. There will be particular emphasis on those aspects about which there is most uncertainty. ... Prototypes are used to verify the accuracy of the assumptions made about those aspects. In contrast to production systems, prototypes are typically incomplete, and are not intended to function faultlessly. (Vonk 1990, pp. 20-1)
Beyer, H. & K. Holtzblatt (1998). Contextual Design: Defining Customer-Centered Systems. San Francisco, CA: Morgan Kaufmann Publishers
Bødker, S. & K. Grønbæk (1991). "Design in Action: From Prototyping by Demonstration to
Cooperative Prototyping", in Kyng, M. & J. Greenbaum (Eds.), Design at Work (pp. 197-218). New Jersey: Lawrence Erlbaum Associates
Ehn, P. & M. Kyng (1991). "Cardboard Computers: Mocking-It-Up or Hands-On the Future", in Wardrip-Fruin, N. & N. Montfort (Eds.), The New Media Reader (pp. 651-62). Cambridge, MA: The MIT Press
Vonk, R. (1990). Prototyping: The effective use of CASE technology (pp. 20-33). Englewood Cliffs, NJ: Prentice Hall Inc.