Great Video as usual!
It seems to me like this exists more on a spectrum though.. from what you're saying, if a choice has any weight behind it... that is, if one choice can be considered preferable, then it's a "problem in disguise", to me that makes it seem as though the only thing that you could call a real grade A USDA approved "choice" would be something that has zero impact on the game.
Like, if a character early on asked you to choose sides in a dispute and depending on which side you choose, a race of people later on in the game all have red hair instead of yellow hair, then it's a choice I suppose unless you prefer one color to the other, in which case it would become a problem because you'd want to make the "correct" choice, the one that would yield your favorite color.
The thing is, I don't see any decision as worth making if I don't have something invested in the outcome...like say if I were colorblind, then the hair color would be irrelevant. The same goes for "choices" that would create branches in the gameplay...if a decision in a game gives me branching paths, people will have preferences as to which branch is more to their liking. Like Castlevania 3 to a degree, moreso if you took the extra characters out of the equation.
So I see it as any given decision either being closer to a choice or problem based on how much weight is given to the outcome. In order for something to be a pure "choice" by what I see as your definition, it would have to be totally inconsequential and therefore meaningless, like naming your main character with the stipulation that the name never appears in the game because if it did... it might move into problem territory since I'm sure there would be some name you'd prefer to see for whatever reason.