My method is to get 3 random craigslist people and pay them $50 bucks to play with the app for an hour. Record them struggling and have them talk through their thoughts and how they use your app. You will learn more from that experience than anything else.
The 'obvious' lock screen camera thing on the iPhone is a perfect example of something that I haven't seen anyone figure out on their own. It doesn't look or behave like anything else on the iPhone, including the only other interactive element in that same lock screen. Once you DO know, the cues are nice reminders.
The Pudding Monsters example is terrible too, as it precisely a UI walkthrough. Minimal, because well, the UI in that game is minimal, but it is explicitly telling you what to do and how to do it. (BTW the game is wonderful)
I think I had even read about it, but never bothered to try it until now.