If you have 2 minutes to solve a puzzle, is it no longer a puzzle game?
Yes, clearly. It still behaves the way a puzzle - or puzzle game - would: knowledge of the solution trivialises the content. It's just a puzzle game with a timer.
If moving certain colored pieces requires a button combo or sequence, instead of a simple action, is this no longer a puzzle game?
Depends on how the combo works. Is there an element of skill involved? If it's like a rhythm game I would just call it a puzzle/rhythm game. Otherwise it's just a puzzle game with extra steps.
For me, if the main challenge of the game is figuring out the puzzle, then it's mainly a puzzle game. If a measure of skill is required in the actual execution of beating the game it is no longer a pure puzzle game - but it can still contain puzzle elements of course.
EDIT: I would agree that Tetris is not a puzzle game.
Knowing the optimal thing to do can be seen as but a higher order puzzle.
But knowing the right strategy and item build in DotA or LoL means fuck all if you can't mechanically execute your hero properly, which - in my opinion - disqualifies them as "puzzle games".