Let me answer your concerns point-by-point:
Isn't there a minimum size for this?
Big design up front must be more
efficient for a three or four week
project... Right?
I'm not sure what makes you think that drawing rectangles on paper must be faster than refactoring code.
Anyway, even if it was, the question of whether BDUF pays back would be much more a function of how much learning you expect during the project than of project size. The more you can expect to learn something about the design, the requirements, etc. while implementing the system, the more your up front design becomes wasted.
I have yet to encounter a project where I didn't learn significant things while implementing the system.
Our customers usually require fixed
prices. They need to know what they're
dealing with, except in special cases
where we are up against an obvious
black hole and even then people are
more comfortable with a cap. So how
can you provide a quote if you're
going with a process that is tolerant
of ongoing requirement changes?
Only accept requirement changes that don't change total effort. That is, when new requirements come in, drop less important ones. Let the customer decide so that he can get the most bang for the buck.
You won't get all benefits of Agile this way, but it's as good as fixed price can get, as far as I can tell.
I understand that Agile may provide better odds of success in more complex projects, but won't it drive up costs to the customer?
Are you suggesting that projects run the Agile way are more costly than traditional projects? There are actually companies out there that experienced the opposite, up to a cost reduction by 50%.
And of course there is the cost of failure to consider - perhaps we are back at the minimum size question here.
Cost of failure goes down with an Agile project, because of the early feedback. You can notice failure - and therefore decide to cancel the project - much earlier.
How in the world would you explain this counter-intuitive approach to customers? Non-technicial stakeholders might not have the experience to wrap their heads around anything beyond Waterfall.
Why does Agile Software Development pay?
Even for internal projects, there are budgets. What am I missing?
I don't know. Agile works fine with budgets - implement the highest priority features until the budget is used up. You have the most valuable system that could have been implemented for that money.
It seems like there is some backlash against Agile lately. Is something else going to start gaining traction soon?
There has been backlash against it from the very beginning. And as it's becoming more popular (and it is!), it's just natural that you also see more backlash.
Lean Software Development is gaining a lot of traction. It's not in competition to Agile development, but rather complementary, though. The communities actually are quite overlapping.
Regarding the "one methodology to rule them all" - take a look at Alistair Cockburn's "Crystal" family of Agile processes. He argues (quite competently) that every project needs it's own process, and that even one project's process needs to change over the course of the project. And he provides a lightweight framework for developing your process.
As does Scrum, as I think about it. Scrum actually doesn't tell you very much about how to run your project, but much more about how to find out what's working and how to enable the team to adapt to those findings.