As we should expect the following identity (maybe under some certain mathematical assumptions, I'm not sure):
$$\sum _i \sum _j f(i,j)=\sum _i \left(\sum _j f(i,j)\right)\;\text{,}$$
which we can confirm in Mathematica 9 by the examples say:

However, the nested-iterator version of the summation in the original question takes forever time in my Mathematica 9:
Sum[1/((k + 2)*k!),
{n, 0, Infinity}, {k, n, Infinity}]
while the nested-Sum
version
Sum[
Sum[1/((k + 2)*k!),
{k, n, Infinity}],
{n, 0, Infinity}]
as Mark McClure said in answer above, and user0501 said in comment, evaluates quickly to 1 + E
.
So for the " Why the difference? ", my guessing is maybe Mathematica uses different algorithms and strategies for this two different kind of summations, which eventually make the former one unable to reach the answer for OP's problem.
Note
I believe it's a bug or something that in some Mathematica version exchanging the iterators works.
Have a look at the following snapshot taken from Mathematica 9:

The upper one, i.e. the iterator-exchanged one, has a lighter-green n
under the most left $\sum$, which indicates it's a free global symbol, against the correct situation where it should be a iterator symbol with celadon colored. So $k$ gets wrongly out of the scope of $\sum_{n=0}^\infty$ here.
1 + \!\( \*UnderoverscriptBox[\(\[Sum]\), \(n = 0\), \(\[Infinity]\)]\( \*UnderoverscriptBox[\(\[Sum]\), \(k = n\), \(\[Infinity]\)] \*FractionBox[\(1\), \(\((k + 1)\) \(k!\)\)]\)\)
. This by the way does not converge in Mathematica 9 and in place of1 + e - Cosh[1]
returns the input unchanged. TheSum
version does converge to $\mathrm e$. $\endgroup$1 + \!\( \*UnderoverscriptBox[\(\[Sum]\), \(n = 0\), \(\[Infinity]\)]\(( \*UnderoverscriptBox[\(\[Sum]\), \(k = n\), \(\[Infinity]\)] \*FractionBox[\(1\), \(\((k + 2)\)\ \(k!\)\)])\)\)
$\endgroup$1 + Sum[Sum[1/((k + 2) k!), {k, n, Infinity}], {n, 0, Infinity}]
and1 + Sum[1/((k + 2) k!), {n, 0, Infinity}, {k, n, Infinity}]
They should give the same answer but they don't. $\endgroup$