So I have this false proof and I am honestly confused why this is happening.
Consider $x^2+x+1=0$, then $x+1=-x^2$.
Now by simply dividing the equation by $x$ we get $x+1+1/x=0$. Substituting $x+1=-x^2$ we get $-x^2+1/x=0$ we get $x=1$ as a solution. Why is this substitution introducing a new solution, 1? Is it that all the solutions must fulfill this equation, but it is not a sufficient condition to actually be a solution? Why?
I think this might be a really silly question but it is stomping me :P
Yes, exactly right. Substituting one equation in another has the potential to introduce more solutions, because you've thrown away information. Specifically, you threw away the original equations you were given. A solution to the original equation will be a solution to your new one, but the new one may have others.
For a silly example, consider $$ x + x = x + 4. $$ There is only one solution to the equation: $x = 4$. But suppose we substitute $x = 4$ on the left side for one of the $x$'s; then we get $x + 4 = x + 4$, or $4 = 4$, which has infinitely many solutions (every real number $x$).
In your example, you ended up with the equation $−x^2+\frac{1}{x}=0$, which is equivalent to the equation $-x^3 + 1 = 0$ (assuming $x \ne 0$), or $x^3 - 1 = 0$. This factors as $x^3 - 1 = (x - 1)(x^2 + x + 1)$ (as was pointed out in a comment), so you have introduced exactly 1 new solution.