How do we measure progress?

One of the things waterfall projects have over XP projects is Gantt charts. In the middle of the project they give your customer confidence that you are proceeding according to schedule. they put off the pain until the end when the charts need to be extended by testing and such.

In XP we can only tell them what we did. Customers want a measure that tells them you did as much this month as you did last month and how much is left and how long it will take. Velocity measures yesterdays weather. On other projects we have capped the budget, and report what we think the last story will be.

On this project we want to cap the time, complete a specified number of stories (2400), and budget is less of an issue. We don't do design up front - we do incremental requirements (stories). The last couple of sprints, our velcoity has decreased. In our estimation the stories have gotten bigger (have more pieces to them). What can we use to be honest with ourselves? Have our stories gotten bigger? Or has our code become more complex and we've slowed down? How do we measure this so we don't lie to ourselves? How do we measure this so we can explain to the customer?