You can decompose the exponential distribution into a sum of two terms, which are not both gamma distributed.

Let A,B,ε be independent where A,B are exponentially distributed and ε takes the values 0,1 each with probability 1/2, and set X=A/2, Y=εB. You can calculate the moment generating functions of X and Y,
$$
E\left[\exp(-\lambda X)\right] = E\left[\exp(-(\lambda/2)A)\right]=1/(1+\lambda/2).
$$
$$
E\left[\exp(-\lambda Y)\right]=(1/2)E\left[\exp(-\lambda B)\right]+1/2=(2+\lambda)/(2+2\lambda).
$$
Then you can check the moment generating function function of X+Y, E[exp(-λ(X+Y)]=E[exp(-λX)]E[exp(-λY)]=1/(1+λ) to see that X+Y has the exponential distribution.

Edit:
After reading at Michael Lugo's response below, it might be more satisfying to have an answer where neither of X or Y are Gamma distributed. In fact, by iterating my argument above you can get the following example. If A_{1},A_{2},... have the exponential distribution and ε_{1},ε_{2},... take values 0,1 each with probability 1/2 (and all these rvs are independent), then X=∑_{n}2^{1-n}ε_{n}A_{n} has the exponential distribution (just check the moment generating function). By splitting this sum up into two smaller sums you can generate a whole load of counterexamples where neither term is gamma distributed.

Edit 2: Apologies for keeping coming back to this one, but it seems interesting and my examples above are a special case of the following.

For any k>0 and measurable subset A of the interval (0,1], you can define a random variable X_{A} with moment generating function E[exp(-λX_{A})]=exp(-λk∫_{A}dx/(1+λx)). If you partition (0,1] into two measurable sets A,B and X_{A},X_{B} are independent, then X_{A}+X_{B} has the Gamma(k) distribution. If A and B are unions of finitely many intervals then the moment generating functions will be k^{th} powers of rational functions of λ and its easy to make sure that X_{A},X_{B} are not gamma distributed. My first example above is using k=1 and the partition (0,1/2],(1/2,1]. The second one, in the edit, is partitioning (0,1] into the intervals (2^{-n},2^{1-n}].

You can construct X_{A} as follows. Let T_{1},T_{2},… be independent with the Exp(k) distribution, and S_{n}=exp(-T_{1}-…-T_{n}). The number of S_{n} in a subset A of (0,1] will be Poisson with parameter ∫_{A}dx/x. If Y_{1},Y_{2},… are independent exponentially distributed then X_{A}=∑_{n}1_{{Sn∈A}}S_{n}Y_{n} has the correct moment generating function. (I'll leave you work through the details...). Alternatively, the set {(S_{n},Y_{n}):n≥1} is a *Poisson point process* with intensity ke^{-y} dy ds/s.