I think (and I may be going out on a limb here) that ALL projects should have a bit of classic waterfall: The initial analysis and specification phase is essential. You must know what you are doing, and you must have it in writing. Getting the requirements in writing is difficult and time consuming, and easy to do badly. That's why so many skip it - any excuse will do: "Oh we do agile so we don't need to do that." Once upon a time, before agile, it was "oh I'm really clever and know how to solve this, so we don't need to do that." The words have changed a bit but the song is essentially the same.
This is of course all bull: You have to know what you are to do - and a specification is the means by which developer and client can communicate what is intended.
Once you know what you have to do - sketch out an architecture. This is the "get the big picture right" part. There is no magic solution here, no one right way, and no methodology that will help you. Architectures are the SYNTHESIS of a solution, and they come from partly inspired genius, and partly hard-won knowledge.
At each of these steps there will be iteration: you find things wrong or missing, and go fix 'em. That's debugging. It's just done before any code got written.
Some see these steps as boring, or not needed. In fact, these two steps are the most important of all in solving any problem - get these wrong and everything that follows will be wrong. These steps are like the foundations of a building: Get them wrong and you have a Leaning Tower of Pisa.
Once you have the WHAT (that's your spec) and the HOW (that's the architecture - which is a high-level design) then you have tasks. Usually lots of them.
Bust the tasks up however you want, allocate them however you want. Use whatever methodology-of-the-week that you like, or that works for you. And get those tasks done, knowing where you are heading and what you need to accomplish.
Along the way there will be false trails, mistakes, problems found with the spec and the architecture. This prompts things like: "Well all that planning was a waste of time then." Which is also bull. It just meant you have LESS foul-ups to deal with later. As you find problems with the high-level early days stuff, FIX THEM.
(And on a side issue here: There is a big temptation I've seen over and over to try to meet a spec which is expensive, difficult, or even impossible. The correct response is to ask: "Is my implementation broken, or is the spec broken?" Because if an issue can be sorted out quickly and cheaply by changing the spec, then that is what you should do. Sometimes this works with a client, sometimes it does not. But you won't know if you don't ask.)
Finally - you must test. You can use TDD or anything else you like but this is no guarantee that at the end, you did what you said you would do. It helps, but it does not guarantee. So you need to do final test. Thats why things like Verification and Validation are still big items in most approaches to project management - be that development of software or making bulldozers.
Summary: You need all the up-front boring stuff. Use things like Agile as a means of delivery, but you can't eliminate old-fashioned thinking, specifying, and architectural design.
[Would you seriously expect to build a 25-story building by putting 1000 laborers on site and telling them to form teams to do a few jobs? Without plans. Without structural calculations. Without a design or vision of how the building should look. And with only knowing that it is a hotel. No - didn't think so.]
You're attempting to repurpose an agile project planning tool into a waterfall one.
I'm no expert, but this is the very problem that Agile intends to address i.e: "Responding to change over following a plan". "Going Agile" involves something of a tradeoff - exhanging concrete costs and deadlines for flexibility and responsiveness of development. In a nutshell, the customer has to be (delicately) asked the following question:
Which of these is more important to your business, the features or the
delivery/cost?
NB: This is an abbreviation of a commonly accepted rule of thumb, see Thomas Owens comment below re: project management triangle. I chose to present a slightly more cynical slant on it...
Inevitably, clients want both, but armies of burnt out developers/agencies shows that up front estimation rarely matches the reality of execution and generally this leads to hideous overtime or "late" delivery and angry clients.
The whole point of Agile is that it is an attempt to bring an element of empiricism to delivery dates, measuring performance in terms of velocity relative to "task complexity". IMO the problem is that you've equated story size with hourly estimates. The meaning of story size is entirely dependent on how you break them up, which is why 1-5 is not already presented as a unit of time (unlike typical estimation tools).
If they absolutely need a concrete estimate, then they are not ready for an Agile relationship, so use the time honoured method of padding out of your schedule, and hope that the competition is putting in more padding in than you.
As I said, I'm no expert, but I've been through a experience to the one you're describing, and I asked a similar question then too: Funding Agile Projects
EDIT: JFTR - I heartily endorse Pivotal Tracker, we used it extensively on the last project I worked on, but it was something of a paradigm shift for the management/sales team to get their head round...as illustrated by the thread above, Agile is not such an easy sell outside of the dev/enterprise community
Best Answer
I just pushed my organization to pilot an agile approach on one of our projects. It was a challenge for senior management because they need a projected budget and timeline before they can even get a project funded (it's a large enterprise-y company).
So, I did what I always do in that situation, make an educated guess. I looked at the scope we were assuming the project would entail, guessed at the development time of those items, added in some additional time for business analysts, DBAs, project manager, etc., added some padding, and called that the estimated budget. Note that this kind of "rough order of magnitude" estimation is done in my company before every waterfall project as well, so it was no different.
Then, as we started the agile project, and we got a sense of our velocity, we projected the end point of the project based on the velocity and the remaining story points, and found that we are coming in ahead of my original high-level estimates. But that is okay (and we expected it).
So I guess to generalize an answer, it depends on what you mean by "long range", and when you need these estimates. If you need them before the project starts, you can use my method. If you need them during the execution of a project, you can use the release planning concept that Matthew Kubicina mentions.
Also, I highly recommend Mike Cohn's Agile Estimation and Planning book which helps address this kind of stuff.