I think you should select the range before using Selection->Sort. Try the following:

$Range_new1 = $Sheet->Range("m:n");
$Range_new2 = $Sheet->Range("n2");
$Sheet->Range('m1:n1000')->Select();
$Excel->Selection->Sort({Key1 => $Range_new1,
                         Order1 => xlAscending,
                         #Key2 => $Range_new2,
                         Header=>xlYes,
                         OrderCustom=>1,
                         MatchCase => False,
                         DataOption1 => xlSortNormal});
[download]

It's untested, and it should only work for the first 1000 rows, but if it works, you can always determine your last row number using the method described here: 153486 If I get my hands on Excel, I'll try and see if it works, and post my findings, in the meantime, try this. Regards, Luke