I've ran across this topic on 3 occasions in the last week in various forms: online, with a team, and on a LinkedIn board. Wow, must be something in the air.
So here's the short version:
1) Agile relationships with customers boil down to Time and Materials. You're there working sprint-by-sprint doing stuff. Each sprint the customer and the team agrees on what it can do. The team decides, but the customer can always fire them. This isn't estimation, this is just how an Agile engagement is supposed to work.
2) Most Agile teams split estimating into two parts: how difficult it is to deliver, and when it can be done. It's important to understand that by separating these concepts, you're not pressured to make time commitments when spitballing story difficulty. That's a good thing. Decouple those concepts and leave them decoupled.
3) As a trailing indicator, you should use past team performance as an estimate of how the big picture is going to play out. [insert long discussion here about the various ways to do that]
4) None of this is business or contract management. That's another can of worms. Yes, it all gets mixed up sometimes, but there are ways to keep visibility at the right level to let all the players work effectively.
5) None of this will make-up for working in a crappy environment. Sucky situations still suck.
Estimating can be a pain in the ass, but it doesn't have to be. I think we've reached the point where most of the pain is gone if you set the environment up the correct way. (fingers crossed)
Shameless plug: I've got a no-nonsense Agile Tune-Up email series in case anybody's interested. It covers estimation (along with many other Agile team topics) http://bit.ly/15sz0Pl
ADD: As you can tell from the many comments, this is also a topic that has been done to death. There are more methods out there than you can shake a stick at. (Hence my reluctance to dive in with "This is the perfect way to estimate!"). But the key takeaway is this: lots of simple, quick estimates that converge over time beat any kind of complex model done only once. If you only get one thing, that's the thing to understand. We keep trying to "fix" this by creating models, when the real answer is that over time the team learns to estimate each project as a separate entity. The more engaged it is with the problem and the farther along it is, the better the estimates get. It's a funnel. Don't spend a lot of effort trying to polish up the first part of the funnel: rather, make a commitment to using empirical knowledge and re-estimating to provide better and better estimates as you go along. There's a lot more value added to everybody's job that way.
Hell, I don't care if you use KLOC, some kind of FPA, phases of the moon, or your lucky astrology mood watch to estimate, as long as you continue to re-estimate as you go along and your estimates quickly converge on the actual result.