What I've found most people do wrong is start with unit tests, which test implementation not deliverable, then realize after writing a bunch of code they did it wrong.
I tend to write the acceptance test first.
e.g. #1 If I'm writing a web app I write a selenium test "as a user, when I click the button, I see X".
e.g. #2 If I'm writing a distributed database, I write a test "state should converge".
These acceptance tests (aka end-to-end, UAT, UI test) ensure the desired end state is tested for, then I work outside-in to create implementation, writing unit tests as needed along the way.
When I find people fail at TDD, it's usually due to the lack of knowledge, ability or infrastructure to approach the problem this way.
Small stories in the correct order are also critical. I agree with the "risk first" approach an article on HN described yesterday.
Source: I taught a course on TDD to some big enterprise clients.