How do Jehovah's Witnesses explain John 8:58-59 in a way that accords with their doctrine? The Jehovah's witness' version of the bible the NWT translates these verses as:


  58 Jesus said to them: “Most truly I say to you, before Abraham came into existence, I have been.” 59  So they picked up stones to throw at him, but Jesus hid and went out of the temple. (emphasis added)


KJV,ESV,NIV,NRSV,NASB all translate the bold section in v58 as "I am", (source) which on the surface, seems to be a direct reference to the way God revealed himself to Moses at the burning bush:


  13 Moses said to God, “Suppose I go to the Israelites and say to them, ‘The God of your fathers has sent me to you,’ and they ask me, ‘What is his name?’ Then what shall I tell them?”
  14 God said to Moses, “I am who I am. This is what you are to say to the Israelites: ‘I am has sent me to you.’” - Ex 3:14-15 NIV (emphasis added, cf. v14 in different versions)


As such, it would seem logical for the Jews to want to stone Jesus for (in their eyes) blasphemy.

This Q&amp;A on the biblical hermeneutics site addresses which translation of those particular words is preferable, so I don't wish to re-hash that ground, but to ask, given the sense imparted by the following verse (i.e. that the Jews regarded what Jesus was saying as blasphemous) how can it be logically maintained that Jesus was not referencing the name (or title, or description - that particular distinction should be irrelevant) of God as revealed to Moses at the burning bush and applying it to himself?
I actually do not see a problem here. The Jehovah's Witness group teaches that God the Father created Jesus first (source), then Jesus created everything else (source). So they do believe that Jesus existed before his incarnation.

To the Jews, this is an irrelevant distinction. It is blasphemous either way. 


"Jesus is God" = blasphemy - stone him
"Jesus was created by God before everything else" = blasphemy - stone him.


Anything about "I am" being in reference to God the Father, explicitly, is simply denied and translated accordingly in their New World Translation. Whether their translation is valid or not is a question for the Hermeneutics site.