Here is a partial answer to for the case of regular graphs of odd degree which expands on my comment above.
Basic Fact. If $G$ is a $(2r+1)$-regular graph, then $G$ has $r$ edge-disjoint $2$-factors iff $G$ has a $1$-factor.
Indeed, what is left after deleting $r$ edge-disjoint $2$-factors is a $1$-factor. Conversely, after deleting a $1$-factor, what is left is a $2r$-regular graph which has a decomposition into $r$ edge-disjoint $2$-factors by Petersen's theorem.
As I pointed out in the comment above, Tutte's $1$-factor theorem therefore gives an exact characterization of which $(2r+1)$-regular graphs have $r$ edge-disjoint $2$-factors.
Another result of Petersen says that every $2$-edge connected cubic graph has a $1$-factor. (More generarlly, every $2r$-edge connected $(2r+1)$-regular graph has a $1$-factor.) This can be used in the hunt for a counterexample.
Take any cubic graph $G$. Select a vertex $v$ and let $e_1,e_2,e_3$ be the three edges connected to $v$. Insert a new vertex $v_i$ in the middle of $e_i$ and attach from $v_i$ the following graph
| X o---o
where the vertex of degree 1 on the right is $v_i$.
The resulting graph $H$ is a cubic graph with no $1$-factor (and hence no $2$-factor). Indeed, a $1$-factor $M$ of $H$ would need to contain all three dangling edges from the three copies of the 6-vertex graph pictured above. Therefore, $M$ cannot contain any edge obtained by splitting one of the three edges $e_i$ at $v_i$. So $M$ actually induces a $1$-factor of $G$, but this is impossible since a $1$-factor of $G$ must contain one of $e_1,e_2,e_3$.
Taking $G = K_4$ leads to a counterexample with $22$ vertices. Perhaps a similar trick can be used to produce $(2r+1)$-regular counterexamples for $r \geq 2$?
[I would be very grateful if someone generously volunteered some nice pictures here.]