field solutions for covariant derivative of vector field constrained to zero Question:

What do the solutions of $\nabla_\mu A^\nu = 0 $ look like?
  And is it possible for spacetime curvature to somehow restrict the solution to $A^\nu = 0$?

Here is my current understanding and thoughts.
If a scalar field had a constraint in the form of the partial differential equation:
$$\partial_\mu \phi = 0 $$
Then the only solution is $\phi$ is constant.
For a covariant derivative instead:
$$\nabla_\mu \phi = 0 $$
The solution is the same, since for a scalar field the covariant derivative is just the ordinary partial derivative.
Now, what about a vector field?   

What exactly can we conclude about a vector field if its covariant derivative is everywhere zero?

For a vector field:
$$\partial_\mu A^\nu = 0 $$
means each component is constant.  But with a covariant derivative:
$$\nabla_\mu A^\nu = \partial_\mu A^\nu + \Gamma^\nu{}_{\mu\lambda} A^\lambda $$
So a non-zero constant $A^\nu$ will not work when the Christoffel symbols are non-zero.
Since (the product rule holds, right?):
$$\nabla_\mu A_\nu A^\nu = \nabla_\mu \ g_{\lambda\nu} A^\lambda A^\nu = A^\lambda A^\nu \nabla_\mu \ g_{\lambda\nu} + 2 g_{\lambda\nu} A^\lambda \nabla_\mu A^\nu = A^\lambda A^\nu \nabla_\mu \ g_{\lambda\nu} $$
Assuming the simple case of a metric compatible connection, that means:
$$\nabla_\mu A_\nu A^\nu = 0 $$
And since $A_\nu A^\nu$ is a scalar, then the magnitude of $A^\nu$ must be constant.
I have trouble visualizing these solutions.  
If space-time is flat, then I can choose a coordinate system where the Christoffel symbols are zero everywhere, and therefore the components $A^\nu$ are all constant.
For curved space-time I could see there being issues like with the hairy-ball theorem, such that there is no way to have $A^\nu$ with a constant magnitude everywhere and also non-zero without running into contradictions.  So it seems plausible that the covariant derivative being zero could actually be much more restrictive and cause the only generic solution to be that the field itself is zero.
With curved space-time, if I choose a coordinate patch in some small region such that $A^\nu$ is always in the z-direction, and scale the coordinates such that the component $g_{33}$ is constant in this patch, then the requirement that the magnitude of A is constant means the  partial derivative of the components $A^\nu$ is zero.  But that in turn means
$$\nabla_\mu A^\nu = \partial_\mu A^\nu + \Gamma^\nu{}_{\mu\lambda} A^\lambda = \Gamma^\nu{}_{\mu\lambda} A^\lambda = 0  \quad \implies \quad \Gamma^\nu{}_{\mu 3}  = 0 \ \ \mathrm{or} \ \ A^\lambda = 0 $$
It does not appear to me that the scaling of the coordinates to make $g_{33}$ constant, would cause this.  So this appears to be a derived condition on either the geometry, or a requirement that $A^\nu=0$.

So is flat space-time somehow very special here?  Is the only solution $A^\nu=0$ except for some very special space-time geometries?  What do these solutions and special geometries look like?

 A: You basically have the right idea: the existence of a covariantly constant vector field is a big restriction on the metric. 
You already discovered that $A^a$ has constant norm. The next thing we find is that $A^a$ is a Killing vector, because obviously $$\nabla_{(a}A_{b)}=0.$$ Furthermore, $A^a$ is geodesic, $A^a\nabla_a A^b=0$, and hypersurface orthogonal, since the Frobenius integrability condition is $A_{[a}\nabla_b A_{c]}=0$.  
This means we can write $$A_a=N \nabla_a Z$$ for some scalar functions $N$ and $Z$. In fact, $N$ must actually be a function of $Z$. One way to see this is from $$\nabla_{[a}A_{b]}=\nabla_{[a}N \nabla_{b]}Z=0$$ which implies that the gradients $\nabla_a N$ and $\nabla_aZ$ are linearly dependent. So by re-defining $Z\mapsto Z'(Z)$, we can write $A_a=\nabla_a Z'$, i.e. get rid of the $N$. 
Now, we can use $Z'$ as one coordinate, and pick the the other coordinates so the $A^\alpha\propto\delta^\alpha_{Z'}$, with a constant "constant of proportionality." Then since $A^a$ is a Killing vector, the metric components in this coordinate system must be independent of $Z'$. Also, we have chosen coordinates such that $g_{Z' \beta} = 0$ for $\beta\neq Z'$.  
You can then see that we get a metric for a manifold that is flat along the direction of $A^a$.  So the manifold must locally be of the form $\mathbb{R}\times M$ or $S^1\times M$ (in general it could have the structure of a $U(1)$ or $\mathbb{R}$ fiber bundle, which may have nontrivial topology). The line element is then $$ds^2=Cd{Z'}^2 + h_{ij} dx^i dx^j,$$ where $C$ is a constant and the transverse metric $h_{ij}$ on $M$ is independent of $Z'$. So we do in fact find some very nontrivial restrictions on the metric whenever there is a nonzero, covariantly constant vector $A^a$. 
