Ilomilo
Ilomilo isn't just a Lost Vikings-style platform/puzzle game with a sickeningly charming aesthetic and clever puzzle concepts -- it also has collectibles! Well, not that many collectibles, but enough to unlock special stages and other bonus content.
It's pretty neat. You should try it!
Progress: Played the trial