Alright, I've had a day or so (a very hectic day) to digest some of the responses, and I'd like to clarify some of my thoughts on the matter.
To start, I do not wish in any way to trivialize the intellectual accomplishments of preliterate cultures. Preliterate folk mastered the use of energy to transform the chemical structure of substances like rock and clay to produce stone tools and pottery. This sort of heat treatment is a fundamental step (in a long series) towards modern chemistry. Preliterate folk also laid the groundwork for modern medicine (by amassing an immense oral pharmacopoeia of substances occurring in nature, and by pioneering feats of surgery like trepanation). They also provided the foundation for navigational systems through their observations of the heavens, which not only allowed them to isolate their location in geographic space but also allowed them to mark the passage of time. All of these things were discovered long before the dawn of recorded history.
But they did not (and do not) reckon the passage of time in the same way that literate folk do. Premodern and preliterate societies often have a cyclical conception of time against our linear conception. This is the basis for astrology -- the stars can determine the fates of mankind simply because what has happened before will happen again, in an eternal never-ending cycle. That is precisely what people mean when they say that "the stars are in alignment" for a given event; they are depending upon past experience to predict the future, which makes little sense from a linear perspective, but complete sense from a cyclical one.
Remember what I said about the "homeostatic present" of illiterate folk. Illiterates live in a kind of perpetual present that survives by acquiring and jettisoning vocabulary as they see fit. This is largely because there are cognitive limits to the amount of vocabulary that an individual can control, and when there is no written language, the conceptual boundaries of a language are limited by the vocabulary of its living speakers. The Oxford English Dictionary contains 301,100 main entries, for example; it is unthinkable for a single person to master more than a tiny fraction of those entries (let alone use them productively), which obviously limits his ability to retain and transmit information accurately. Bear also in mind that the energy required to retain and accurately transmit information orally is staggering (imagine being forced to compose a timeline without reference to Wikipedia or any books, and you'll get an idea of the task facing a preliterate savant). As knowledge in an oral culture tends to disappear unless it is frequently repeated, oral cultures must invest great energy in repeating knowledge that has been acquired over the ages over and over again. As a corollary, oral compositions are always directed towards a particular audience, as it would be pointless to deliver them while alone. This need encourages and even demands a highly traditionalist or conservative mindset that shuns intellectual experimentation, and for good reason. I do not intend to suggest that oral cultures are bereft of creativity or originality, but merely that this creativity consists chiefly of variations upon established themes.
Also, knowledge is rarely presented in the abstract, but almost always in reference to situations derived from the human experience. This brings me to another issue that some of you brought up: that of religion. "Religion," in its most basic sense, essentially entails a system of beliefs surrounding mankind's relationship with the supernatural. This relationship is derived from the human experience, and is expressed largely in terms of metaphors (which are a universal way for mankind to make sense out of something, by expressing it through analogy to something else). In this light, religions arise precisely because of the need to make sense of abstractions by expressing them through references to the concrete. That is why so many preliterate societies have anthropomorphic gods who live more or less like humans do, with the same needs and behavior, and describe invisible phenomena (such as disease) through metaphors (divine wrath in the form of poison arrows, or magic spread through the principles of similarity or contagion).
Could complex systems of belief have arisen in an oral society? Well, yes and no. Bear in mind that Buddhism (to give one example) did not spring fully grown like Athena from the head of Zeus. The Buddhism(s) with which we are familiar today is (are) very much the product of millennia of literacy, and is (are) very much a product (products) of the cultures and civilizations which have nourished it (them). Likewise, it is clear that in the case of Judaism and Christianity that the religions in the book are not exactly the same as the religions of the book. They may be connected through lineage, but that lineage is extremely attenuated, and it is precisely the contact with literacy that has made Judaism, Christianity, Islam, and practically every other major religion what it is today. The early Judaisms and Christianities, before the emergence of writing and the canon, were very different from their contemporary manifestations.
Finally, some of you mentioned the Inca as a possible counterexample. I could have easily mentioned (in my own part of the world) the Uruk civilization, which covered a similarly large area and was distinguished by its own impressive accomplishments in many areas. The point I'd like to make here is that there is no sharp division between literacy and orality, but rather a spectrum of orality. Just as many of you have noticed that some people who are ostensibly a product of literate cultures think and behave in many respects like illiterate folk, so too does the literacy spectrum extend into illiteracy.
Writing is, essentially, an organized system employing symbols rather than speech for the purposes of communication. At its most basic state, there is a precise correspondence between the spoken word and the symbol or symbols used to represent it, such that anyone who is familiar with the language and has been trained in the "code" used to represent it will be able to read any written text. Nevertheless, writing has its own prehistory---artwork such as the cave paintings from Lascaux represents a clear attempt to render information symbolically in the absence of written language. I can easily imagine some palaeolithic bard illustrating the tale of a great hunt or war between rival tribes through reference to the paintings, but unfortunately these tales have been lost to us.
Likewise, notched sticks and stones found throughout prehistoric sites likely represent another kind of effort to retain information by representing it symbolically. What do they represent? The passage of days? The number of animals killed? Unfortunately, without the creator to "decode" the message for us, we will never know. That is what separates this "proto-writing" from writing proper.
Uruk had a similar form of proto-writing: small clay tokens, each representing something (a head of sheep, a barrel of grain, a jar of olive oil) which were then embedded in a clay envelope. These envelopes were then stamped by the owner of the goods to ensure that his tokens were not tampered with. Eventually, it became necessary to check the contents of the envelope without breaking it open (say, for example, for the purpose of levying duties, or transshipments of the goods to further destinations), and so representations of the tokens were impressed upon the surface of the clay envelope. This developed rather organically into the cuneiform writing which characterized the region after Uruk.
Likewise, it is almost certain that the Incan quipus, the Vinča "script," and the Indus valley "script" were all forms of proto-writing, if not legitimate writing systems of their own. Unfortunately we do not know whether it is possible to decipher them or not; if they represent proto-writing, then it will be impossible to decipher them, but if they represent writing, it should be theoretically possible to decipher them, especially if we have access to the language of their creators. That is why I would not classify proto-literate societies like Uruk, the Inca, or the Indus valley in the same category as pre-literate societies, if indeed they were proto-literate and not simply literate, as some people might suggest.
