This apparent contradiction can be resolved without the documentary hypothesis. As Bruce Alderman pointed out, Gen 17 is considered an E passage, yet it uses YHWH in the very first verse. Similarly, there are J passages that use Elohim (the very first J passage actually uses YHWH-Elohim). There are certain patterns in Hebrew thought for when one name would be preferred over the other in a given situation.
The Meaning of the Names
YHWH is a proper noun referring to the God of Israel. It is often translated "LORD" (with either all caps or with small caps to keep it distinct from occurrences of "adonai"). Elohim is the generic term for god or gods that only later became a proper name.
As such, YHWH is used whenever the Bible stresses God's personal relationship with His people and the ethical nature of His character. Elohim refers to God's power, His creating all things, and how He is the ruler of all life and all things. Psalm 19 is one of the best examples of how these names are used. The first 6 verses speak of Elohim and His relation to the material world. However, beginning in verse 7, YHWH appears and the focus of the Psalm shifts to the law, precepts, and His relationship with humans who know Him.
The name YHWH is used to show the personal nature of God and how He relates to human beings. On the other hand, Elohim refers to the transcendent creator of the universe, who shaped it. YHWH is appropriate when emphasizing the relationship with Him in personal and ethical matters. Elohim connects deity with existence and humanity.
Accordingly, Genesis 1 uses Elohim to show God's power in creating all things. Genesis 2:4-3:23 uses YHWH-Elohim to show the very intimate and detailed relationship between God and Adam and Eve. Both names are used to show that the same Elohim who created all things maintains a personal relationship with those who walk in His ways. Note that in the very first "J passage," (who is supposed to know God as YHWH) the name is YHWH-Elohim.
However, a complication comes in the verse in question. In Exodus 6:3, God states, "I appeared to Abraham, to Isaac and to Jacob as God Almighty, but by my name [YHWH] I did not make myself known to them.” YHWH is used some 150 times in the patriarchal period. How is this to be made sense of?
The Beth Essentiae
However, a technical point of Hebrew grammar, known as beth essentiae, renders the contradiction moot.* This refers to how a name in Hebrew may not just be a construction of pleasing sounds but refer to a person's essential character and nature. The beth appears at the front of the name El Shaddai, meaning "in the character of the Almighty I appeared to them." Thus, Abraham, Jacob, and Isaac certainly heard and used the name YHWH but it was not until Moses that the essence of the name was revealed. As summarized by Kaiser, "'By the name' is better translated 'in the character [or nature] of Yahweh [was I not known]'" (Kaiser, W. C. 1997, c1996. Hard sayings of the Bible . InterVarsity: Downers Grove, Il). However, Kaiser has now changed his mind about and reads the verse as a rhetorical question, "By my name YHWH was I not known to them?" (Kaiser, The Old Testament Documents: Are They Reliable and Relevant, 142).
Kaiser has changed his stance based on the fact that the Hebrew has the beth only on El Shaddai. He argues that a beth essentiae should be on both names if the second is also to be read as such. However, Motyer argues that the first use sets the stage and it should be understood as on the second. He uses Isaiah 48:9 ("For the sake of My name I delay My wrath, And for My praise I restrain it for you, In order not to cut you off." [NASB]) as an illustration. The governing preposition, "for the sake of" makes better English (and something is required). However, "for the sake of" only appears on the first phrase in Hebrew. We add the "for" to the second for clarity in English. Thus, we do the same for the beth essentiae in Exodus 6:3.
Beth essentiae appear also in Exodus 3:2, 18:4, Isaiah 66:15, and other places. What is perhaps most significant to our study here is the usage in Exodus 3:2. The beth essentiae will be in bold below.
Exd 3:1 Now Moses was pasturing the flock of Jethro his father-in-law, the priest of Midian; and he led the flock to the west side of the wilderness and came to Horeb, the mountain of God.
Exd 3:2 The angel of the LORD appeared to him as a blazing fire from the midst of [in]a bush; and he looked, and behold, the bush was burning with fire, yet the bush was not consumed. [NASB with a modification by this author to show the beth essentiae. NASB transs. it as "in."]
Just as the beth essentiae on flame here shows the nature of God, we can similarly conclude that the same construct is being used in Exodus 6:3 and carry it over to both nouns. Motyer translates the verse 'I showed myself ... in the character of El Shaddai, but in the character expressed by my name Yahweh I did not make myself known.'
Likewise, the Hebrew understanding of shem includes a person's reputation and glory (Brown, Driver, Briggs Lexicon s.v. shem. See Gen 11:4, 12:2; 2 Sam 7:9; Isa 63:14; Dan 9:15; and others.)
The Targum of Pseudo Jonathan and medieval Jewish commentaries take it similarly. TPJ says that the name was known to them, but it was just sounds as the Shekinah glory had not appeared to them. Rashi said that El Shaddai was God's characteristic of giving promises and YHWH showed the fulfillment of said promises. However, Rambam said that El Shaddai demonstrated the providential power of God while YHWH showed the miracle-working power. Umberto Cassuto said El Shaddai referred to God as the giver of fertility (because El Shaddai is connected to Gen 17:1-2 and other passages with being fruitful) while YHWH is the One who carries out those promises. The patriarchs knew the name but they had no experience of what was entailed in the name.
W. J. Martin has suggested this translation.
I am YHWH. I allowed myself to appear to Abraham, to Isaac and to Jacob as El Shaddai. My name is YHWH. Did I not make myself known to them?
Martin argues that the translation of the key clause as a question is demanded by verse 4 beginning with "And also I established my covenant." That would seem to imply that the preceding clause ought to be taken in a positive sense and not a negative sense, such as "by YHWH I was not known to them."
My understanding of Exodus 6:3 is that they knew the name but now they would experience the character of YHWH.
*More information on the beth essentiae can be found in Gesenius' Hebrew Grammar, § 119i. If that is not on hand, Waltke/O'Connor's Hebrew Syntax should have an entry on it. You may also see Zondervan's Pictoral Encyclopedia of the Bible s.v. "Name".