Transforming $x^2-x-1=0$ into $(x^2-1)^2-1=x$ introduces roots that don't solve the original equation. What's wrong with the logic? The equation 
$$x^2-x-1=0$$
has two solutions (the golden ratio being one). However, since 
$$x^2-x-1=0 \quad\implies\quad x^2-1=x$$ 
we have an equation for $x$ in terms of itself. If we take the left hand side which is equal to $x$ and plug it back into the $x^2$ term we get the quartic 
$$(x^2-1)^2-1=x$$ 
This has four solutions (the old solutions with the addition of $0$ and $1$) but these new solutions do not solve the original equation. 

Why is there a logical error in using the equation in $x$ recursively in the way shown?

 A: The problem is, I think, clearer if you take a simpler example.  $$x^2=1\implies 1\times x^2=1\implies x^2\times x^2=1\implies x^4=1$$
but, of course, there are solutions of $x^4=1$ that are not solutions of $x^2=1$.
The problem, of course, is that some of the implications really are one way only.  It is simply not true that $x^2\times x^2=1\implies x^2=1$, all we can say is that $x^2\times x^2=1\implies x^2=\pm 1$. In this way, solutions of the final equation need not be solutions of the original.
As suggested by @IzaakvanDongen in the comments, one can achieve the same sort of example without falling back on complex solutions.  Indeed one could write $$x=1\implies 1\times x=1\implies x\times x=1 \implies x^2=1$$
and, of course, $x=-1$ solves the final equation but not the original.
A: Let's set $f(x)=x^2-1$. Your original equation is $f(x)=x$, and it's got, as you said, two solutions. Your new equation is $f(f(x))=x$, and it's got four solutions.
As already highlighted in lulu's answer: your new equation is just implied by the original one: if $f(x)=x$, then $f(f(x))=f(x)=x$. Your new equation is, however, not equivalent to the original one, because the opposite implication is not valid.
Namely, if $f(f(x))=x$, it may be that actually you have $f(x)=y$ for some $y\ne x$, and also $f(y)=x$. In other words, function $f$ doesn't have $x$ as its "fixed point". instead it swaps it with some other value $y$. Then, obviously, $f(f(x))=f(y)=x$, and $f(f(y))=f(x)=y$, so $x$ and $y$ are two additional solutions. In our case, $f(x)=x^2-1$ "swaps" $0$ and $-1$, so those two numbers pop up as additional solutions.
A bigger point is that not every transformation of an equation to a different one transforms it to an equivalent equation. If implication is valid only in one direction, you may end up with more solutions than the original equation has. (I have most often seen people do this when they square both sides of the equation.) One way to cope with that is to proceed nevertheless, but to check (at the end) whether the obtained solutions satisfy the original equation, or are those some additional solutions that popped up like in your example.  
A: Note that there is no logical error in saying that  $x^2-x-1=0$ implies $(x^2-1)^2-1=x$ but as in the answer by @lulu there are now other solutions as well. 
A: I likewise got flabbergasted by reinjecting a recursive definition of $x$ into the golden ratio equation and realizing
I had introduced a new root. (In my case, the recursion was $x = 1 + \frac 1 x$.)
The reasons of my surprise was the following fallacy:

I reused the recursion I started from to derive the equation; so I hadn't added any information. So how come I ended up smuggling in a new root?

It is a fallacy insofar as introducing a new root does not come as a result of adding, but losing information.
For example, when you reuse the recursive definition $x = x^2 - 1$ inside this very definition, you obtain
a new recursive definition of $x$ from which you cannot retrieve the one you started from. So you have lost this
information:
$$x = (x^2 - 1)^2 - 1$$
$$\phantom{x} = x^4 - 2\,x^2$$
$$\phantom{x} = x^2\,(x^2-2)$$
Yet, you don't have a contradiction; you have not introduced any new information, just derived a weaker statement.
$${x} = x^2\,(x^2-2)$$
$$x^4 - 2\,x^2 - x = 0$$
$$(x^2 - x - 1)\,(x^2+x) = 0 \iff \left[ x^2 + x = 0 \ \lor\  x = x^2 - 1 \right]$$
And, indeed, if you assume that $x^2 + x \neq 0$ and divide both sides by this expression, you retrieve your original equation.
$$\frac x {x^2 + x} = \frac {x^4 - 2\,x^2}{x^2 + x} = x^2 - x - 1 + \frac x { x^2 + x }$$
As an aside, notice that you would have obtained some intriguing extraneous roots if you had substituted $x^2 - 1$ for both occurrences of $x$ in the equation.
$$(x^2 - 1)^2 - (x^2 - 1) - 1 = 0$$
$$x^4 - 3\,x^2 + 1 = 0$$
$$(x^2 - x - 1)\ (x^2 + x - 1) = 0$$
The extraneous roots are $\frac {-1 + \sqrt 5}2$ and $\frac {-1 - \sqrt 5}2$.
