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<sub>1</sub>,A<sub>2</sub>,... have the exponential distribution and &epsilon;<sub>1</sub>,&epsilon;<sub>2</sub>,... take values 0,1 each with probability 1/2 (and all these rvs are independent), then X=&sum;<sub>n</sub>2<sup>1-n</sup>&epsilon;<sub>n</sub>A<sub>n</sub> 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&gt;0 and measurable subset A of the interval (0,1], you can define a random variable X<sub>A</sub> with moment generating function E[exp(-&lambda;X<sub>A</sub>)]=exp(-&lambda;k&int;<sub>A</sub>dx/(1+&lambda;x)). If you partition (0,1] into two measurable sets A,B and X<sub>A</sub>,X<sub>B</sub> are independent, then X<sub>A</sub>+X<sub>B</sub> has the Gamma(k) distribution. If A and B are unions of finitely many intervals then the moment generating functions will be k<sup>th</sup> powers of rational functions of &lambda; and its easy to make sure that X<sub>A</sub>,X<sub>B</sub> 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<sup>-n</sup>,2<sup>1-n</sup>].

You can construct X<sub>A</sub> as follows. Let T<sub>1</sub>,T<sub>2</sub>,&hellip; be independent with the Exp(k) distribution, and S<sub>n</sub>=exp(-T<sub>1</sub>-&hellip;-T<sub>n</sub>). The number of S<sub>n</sub> in a subset A of (0,1] will be Poisson with parameter &int;<sub>A</sub>dx/x. If Y<sub>1</sub>,Y<sub>2</sub>,&hellip; are independent exponentially distributed then X<sub>A</sub>=&sum;<sub>n</sub>1<sub>{S<sub>n</sub>&isin;A}</sub>S<sub>n</sub>Y<sub>n</sub> has the correct moment generating function. (I'll leave you work through the details...). Alternatively, the set {(S<sub>n</sub>,Y<sub>n</sub>):n&ge;1} is a <em>Poisson point process</em> with intensity ke<sup>-y</sup>&thinsp;dy&thinsp;ds/s.