The usability & user experience disciplines are probably the best example of why ‘fail fast’ is a bad idea. If you’ve taken the time to train your users in how to use an application, you can’t then throw it all out the window and start again. Designers will, rightfully, spend as long as it takes to get the interface as perfect as possible.
With ‘agile’ interaction design, there is still a need for an initial design step, to identify the personas and goals that are important to the success of the project. By identifying the basic needs of the users (the traditional requirements gathering step), the first design efforts can have a high certainty of ‘getting it right’, and allow the developers to get started, building the core functionality.
From there, using both the business and user requirements, an iterative approach can deliver the project. Iterations will prevent the design and development efforts going off on a wild tangent, and the amount of re-work will be limited.
There’s a good article here which goes into far more detail about how agile interaction design can work.