The point of Penguin Land is not to move a character from Point A to Point B, it's to use a character to move an egg from point A to point B. If you dispute that it's a puzzle game, I'd be shocked if you played it. It's more puzzle than it is platformer, really.
Also, according to your definition, Doom is a platformer.Similarity to Tetris is irrelevant. Puzzle games are much older and broader than just well games.
It's true that people do use the genre to describe games that aren't easily defined even if they don't have a real puzzle aspect, though.

