Let $(M,g)$ be a smooth compact Riemannian manifold. Is there a link between the convexity of all injectivity domains and the sign of sectional curvatures? For example, is it true that a compact surface all whose injectivity domains are convex (that is, for every $x \in M$, the domain of the exponential map $\exp_x$ is a convex subset of the vector plane $T_xM$) is necessarily nonnegatively curved ?
For a noninjective map like $\exp$, there are many alternative choices of subsets of the domain where the restriction is injective. For a flat 2torus like $\mathbb R^2/\mathbb Z^2$, one domain for $\exp$ is a square centered at the origin, but there are many others  any shape that tiles the plane by translations in $\mathbb Z^2$ will do. For $\exp$, there is a canonical for vectors whose geodesics don't reach the cut locus. I'll take this to be your meaning. Is there a standard terminology, perhaps even "injectivity domain" as you used? Even if so, I think it is misleading, so I'll refer to it as the precut locus. Consider the case $M^2 = \mathbb {RP}^2 = S^2 / \pm 1$. For the standard round metric, the precut locus is the disk of radius $\pi$ in every tangent space. The cut locus remains smooth and convex under small perturbations of the metric, since it's far away from the conjugate locus. But there are also modifications of the metric that make the curvature negative in places without changing the geodesic flow very much. A positively curved metric tends to focus a family of geodesics, making the wave fronts (curves perpendicular to the geodesics) bend toward the concave sense so that the total geodesic curvature of the wave front decreases (by an amount equal to the total Gaussian curvature they sweep through). Negative curvature bends in the opposite way. But just as camera lenses are often designed with both convex and concave elements, you can put some negative curvature into the mix and still make geodesics focus. The cut locus is determined by the shapes of wavefronts at the time they collide, and wherever he net geodesic curvature of any segment is less at the time of collision than the corresponding angle in the tangent space, the precut locus will be locally convex. (But note that to get the full local convexity description depends on geodesics from both sides).
On $S^2$, another phenomenon takes place: the cut locus for the round metric is also the conjugate locus, where geodesics actually focus. In small perturbation of the metric, the cut locus typically becomes a planar tree, which can have arbitrary combinatorial complexity, and can even have infinitely many branches. This is closely connected to the possible cut loci for smooth curves in the plane, that is, the set of centers of disks with interiors inside the curve and boundary circles that touch the curve in two or more points. Added: here is a picture of a cut locus that can occur for a perturbed metric, in a small area near the antipodal point on $S^2$. The computation is actually the Voronoi diagram for 200 points around the image of the unit circle under $z \to .03 z^5 + .01 z^2$. The wave front shown has started to look significantly irregular, but at a radius 100 or even 10 times as large, it would look very nearly round. Cusps are formed at the focal points at tips of trees, and along the edges, wave fronts arrive from two directions at a definite angle. Correction
The same trick can work to get metrics with convex precut locus on $S^2$ even though they have patches of negative curvature: a very localized $C^3$bounded change of the metric can make curvature have localized areas of negativity, but it changes the exponential map near the cut locus by a $C^3$ small amounts. The precut locus will be perturbed by only small $C^2$ amount and remain convex. Added For the case in the figure above, we can see the conjugate locus by drawing rays perpendicular to the curve, showing the geodesics; the fold lines in the picture give the conjugate locus. Each tip of the cut locus is a cusp of the conjugate locus; waves coming from one side of the point focus behind the cut locus. In this case, the conjugate locus is visible as an 8pointed star with 4 long points and 4 short points ending at the ends of the cut locus tree. This figure shows 1400 very thin lines, and shows a larger region than above. Additional: how to visualize the Jacobi equation. The behavior of geodesics is described by the Jacobi equation, which says that the second derivative of signed distance from a geodesic to infinitesimally nearby geodesics equals (Gaussian curvature) times distance. Integrating this equation amounts to taking the limit of composition of sequence of elements of $SL(2,\mathbb R)$, acting on (distance, derivative of distance). This can be visualized by looking at the action of $SL(2,\mathbb R)$ on the hyperbolic plane, which we can coordinatize as the upper half plane $im(z) > 0$. The boundary of the upper halfplane corresponds to the set of slopes of lines in the plane, with 0 corresponding to parallel variations of a geodesic and infinity corresponding to variations of a geodesic that keep distance 0 and turn at an angle. In general, each points on the circle at infinity tell us the curvature of an advancing wavefront. If the point is on the right, the wave front is convex; on the left, concave. If curvature is 0, the point at infinity is fixed, and the action is a unit speed translation to the right in Euclidean terms, a parabolic transformation in hypebolic terms. Curvature creates an additional effect that moves the point at infinity: positive curvature moves it counterclockwise by adding a parabolic vector field fixing 0, and negative curvature moves it clockwise. The instantaneous sum of these two motions is rotation around a point in the positive curvature case, and translation along a geodesic in the negative curvature case. Thus for positive curvature, the wave front shapes make complete circuits around the circle at infinity, alternating between local convexity and local concavity. In the negative curvature case, once convex they always remain convex. I don't want to make this answer even overlier long, but it should be clear from this concrete picture of the Jacobi equation that we can put in smooth little blips of negative curvature without changing the qualitative nature of the wave fronts at the time of the collision that forms the cut locus, and thus not destroying convexity of the precut locus. True but not relevant to the question: 


Given $x\in M$, the domain of injectivity (of $\exp_x$) I am speaking about is the set of velocities $v\in T_xM$ such that the geodesic starting at $x$ with initial velocity $tv$ is minimizing between $x$ and $\exp_x(tv)$ for some $t>1$ sufficiently small. This set is a an open bounded (starshaped w.r.t. $0$) set with Lipschitz boundary in $T_xM$. The image of its boundary by $\exp_x$ is the cut locus (from $x$). I agree that if you perform a $C^3$ perturbation of the round metric on $RP^n$, then the (uniform) convexity of injectivity domains is preserved. But if you perform a modification on the metric (on $RP^2$) to make it negatively curved near some point, you need to do a large perturbation in $C^2$ topology (on the metric). Thus, your geodesic flow will be deformed (much) in $C^1$ topology. You claim that the convexity properties is preserved ? Concerning spheres, it can be shown that under small perturbations of the round metric in $C^4$ topology, the (uniform) convexity is preserved. 

