Software estimation has always been an issue. There's just no way around it, as long as people demand to know long in advance how long a software project is going to take, and especially if they'll get upset if it takes longer. While I appreciate that finance and budgets work a certain way - you have this much money, this much time and this project to do, is it possible? - I also recognise that software is notoriously difficult to predict.
We don't even have a great way to measure software project size. If you're building a bridge, you know how long it will have to be to go from here to there. Estimating a software project is like asking how many blueprints will be needed to design the bridge, but without any clear definition of "blueprint", or even "how many". Probably the best measurement to use is a nebulous Task, which must be broken down far enough that it will probably take an average programmer less than a day to do, and can be clearly seen to be done or not done (never, ever "90% done").
The problem is generating that task list. At that stage of a project, you won't know how big the project is, nor how complex the tasks it requires. To find that out, I think you just have to start. You might not even get a good idea of how large and complex a software project is until it's a quarter of the way complete. The most honest and accurate answer to the feasibility of the project at the beginning is "I can't know".
It seems the only way to get good at estimating software is to spend years trying and failing first, until you develop a good enough intuition about project sizes and how to break them down into tasks.
Once you do have that task list, however, you can start projecting a finish date by using "velocity charts". If you have a record of all your required tasks, then you can track how many are active at any given time and, as long as you're completing them at a rate faster than you're adding them, that graph will, eventually reach zero. If you add a margin around that, based on how far out it is, then you'll get a range estimate for your release date. As that date nears, you'll get more and more certain about exactly when all your tasks will be complete.
Mokalus of Borg
PS - A velocity chart can be depressing if it only goes up.
PPS - Or even if it just stays level.