Grounds for reversal:

Padilla’s sentence is substantively unreasonable because it does not adequately reflect his criminal history, does not adequately account for his risk of recidivism, was based partly on an impermissible comparison to sentences imposed in other terrorism cases, and was based in part on inappropriate factors.

The reasons given for the trial court's sentence:

[T]he conditions of Padilla’s prior confinement, his allegedly low risk of recidivism due to his age at the time of his anticipated release, the comparable sentences imposed on other terrorists, and the fact that Padilla did not personally injure anyone or target Americans in his conspiracy.

The 11th Circuit says terrorists are like sex offenders when it comes to likelihood of recidivism?

Although recidivism ordinarily decreases with age, we have rejected this reasoning as a basis for a sentencing departure for certain classes of criminals, namely sex offenders. We also reject this reasoning here.

“[T]errorists[,] [even those] with no prior criminal behavior[,] are unique among criminals in the likelihood of recidivism, the difficulty of rehabilitation, and the need for incapacitation.” ...Padilla poses a heightened risk of future dangerousness due to his al-Qaeda training. He is far more sophisticated than an individual convicted of an ordinary street crime.

Other complaints:

the district court substantively erred in reducing Padilla’s sentence based on the fact that Padilla did not personally harm anyone and his crimes did not target the United States. The jury convicted Padilla of violating a statute that prohibits any conspiracy to murder, kidnap, or maim outside the United States. We held in a pre-Booker case that a district court may not reduce a sentence of a terrorist because the terrorist committed an inchoate crime.

Lastly, we have held that a district court may reduce a sentence to account for the harsh conditions of pretrial confinement, ...but that decision does not justify a downward departure as extensive as the one the district court gave Padilla.

The Court then shakes it finger at the trial judge:

On remand, we admonish the district court to avoid imposition of a sentence inconsistent with those of similarly situated defendants. It should not draw comparisons to cases involving defendants who were convicted of less serious offenses, pleaded guilty, or who lacked extensive criminal histories, nor should it draw comparisons to cases where the government sought the imposition of the death penalty.

Why bother to have trial judges in the first place if they can't exercise their discretion? Where is the data showing that the recidivism rate for terrorists is similar to sex offenders? Have enough terrorists been freed from prison in the U.S. to even conduct a study?