I love platformer games with puzzle elements that are harder than the typical platformer elements. In recent times I played Toki Tori on WiiWare, which I absolutely loved (I still haven't beat two of the hard levels in the last world).

Wario Land: the shake dimension was good too, it had some stages where the solution wasn't terribly obvious.

Those games often don't get much attention and I don't know many of them. Please recommend some that you liked.

Lost Vikings for the SNES and Megadrive..

And ehm.... Shrek the third for the DS?

Uhm, which platforms are allowed? Because Braid is great (360 and PC).

I'm going to take a look at Lost Vikings... but.. Shrek? I thought it was some kind of stupid mini game?

Yeah, Braid is great, I don't have a 360 though, and can't afford one anytime soon. Good to know that it's PC, too.

Henry Hatsworth in the Puzzling Adventure on DS if you have one.

it's definitely a "puzzle platformer"

SMG?

Yes I have a DS

SMG = Super Mario Galaxy? I have it, played it, love it, but I don't consider it to be a puzzle platformer. There's no focus on puzzle elements in it.