First, as you may already know, Gauss' law is used to find the charge contained within a surface via flux. (Note: I will assume that you are using the integral form of Gauss's law, not the differential, if you do not know what that means, ignore it)
In order to see why it fails, you first must see what they mean by "succeed". The beautiful thing about gauss's law is that no matter what surface you choose to integrate over you will always find the charge contained within it. For example, if I said there was a point charge located at the origin and I gave you its Electric field, you could take a sphere of radius 5 around it, and proceed to use Gauss's Law, and find the amount of charge within it. In fact, you could have taken a cube, a larger sphere, a tetrahedron, and proceeded to use Gauss's law with them. Sure, it would be more difficult computation wise, but in every case you would recieve the the same amount of charge contained within those surfaces.
Now that we know why Gauss's law is great, let us see what would happen if a point charge $q$ varied as $1/r^3$ instead of $1/r^2$. We will compute the flux over a sphere of radius $R$.
$$
\int_S q/(4\pi\epsilon_0r^3)\hat r \cdot dA \cdot
$$
Since the electric field is constant over a given r this means
$$
\int_S q/(4\pi\epsilon_0r^3)\hat r \cdot dA \cdot = q/(4\pi\epsilon_0R^3)* (4\pi R^2)= q/(\epsilon_0 R)
$$
As you can see as a result of my choice of surface, I have gained an extra R term that would not normally be there, thus the geometry of the surface I choose changes the value of the surface integral of the E Field (you can imagine if I integrated over a cylinder or cube, the added terms would look even uglier). In fact, you could imagine that instead of a $1/r^3$ dependence, we make it $e^{\lambda r}$ where $\lambda$ is some constant, and thus the integral would look even stranger, and we could not choose an arbitrary surface to get the same value of charge contained within it. We would obtain strange terms relating to the geometry of the surface. This is what they mean by "gauss's law would fail".