I like HLGEM's answer from a Cover Your ASSets perspective and for reasonable expectation setting on future projects. Having a personal repository of past estimates (both yours and your manager's) is extremely beneficial - both for future productive work and for an unfortunate case where a person needs to dispute an unfavorable performance review. Also the scope management and expecatation setting guidance will work well in many cases, although I think you need to balance caution in whether or not you work over time... based on some details I've put in below.
What struck me, though, was that original question - what does one do at the start when unfavorable estimates are initiated, to correct the issue? - hadn't actually been answered. So, here's some tips that have worked for me:
1 - Listen and ask for Detail
A classic problem in any negotiation is that both sides think they have communicated effectively - which means both sides believe that they have fully understood what the other party was saying and that the other party understands them. Very often, this perception is false. Particularly in the gap between management and technical worker, jargon and process can cause a severe rift.
In the example raised above, I'd be asking the following questions:
Does everyone define "foo" and "bar" the same way? Clearly the employee sees "fooing the bar" as something that raises issues A, B, and C. WHY doesn't the manager see "fooing the bar" the same way?
Do we all agree on the likelihood of issues A, B, and C? Maybe the manager sees them as a 5% chance, while the employee knows there's an 80% chance of these things happening. Why doesn't the manager see them as an issue? Why does the employee? It's not usual that processes or technology have changed since the last time the manager actually did this type of work (if he EVER did this type of work...) and he may rightfully think of these things as minor - based on the information he has available.
Do issues A, B, and C matter? How much do they matter relative to finishing the work on time. Can we call call it "done" if A, B and C are still open issues? Why? Why not? As both a manager and an employee, some of the hardest debates have been these. As a manager I've gone both ways - I've delayed schedules based on employee explanations of why the issue is catastrophic, and I've told employees to suck it up, and leave the issue open in other cases - this is where I figure I earn my pay as the boss - I know when to fix or not fix something because I understand the business and the tradeoffs involved.
Why the crunch? Very very few managers I've spoken to who are worth any degree of respect will willingly burn out their people to accomplish a job. In cases where you are at the "just get it done" level of negotiation, you should still ask "why". If the answer boils down to "because we will all be out of a job in the next 6 months if we don't" - then it may be time to consider overtime and dropping everything. Be aware, though, that your boss is only allowed to play the crisis card once a year or so... if you have a make or break emergency every month, then you have to start asking more questions like "why didn't we see this coming?", "do we really understand the business and it's customers?" and "what on earth in going on in the executive board room? Are you all smoking something?"
a related but different question is "what will happen if I blow this schedule?" Estimates are done for all kinds of reasons... in one case, knowingly blowing a schedule can lead to inefficiency, because a different approach may have been taken if the real schedule was known. In others, it's merely a measurement and management mechanism - a way to set goals and expecations. This factors into project management stuff - like the "critical path", but if your manager is worth anything, he should be able to explain the critical path in terms that go beyond Microfot Project 101 and speak to the actual business drivers for your company.
2 - Speak to the Audience
One of the riskiest thing about a formerly technical manager who thinks he knows how to do your job is that he probably knows more than enough to be dangerous. The terms of technology tend to sound similar from decade to decade, while the actual activity can change remarkably.
This is a touchy area, since you don't want to ask the boss if he actually knows what all the words in your sentence really mean. Instead, you have to look for cues that the words he's throwing around show a marked disconnection from reality as you know it. Then you need to backup and redefine them with him. Often this can be done gently with connection phrases like "here's how I define what you just said..." or "let me take this a deeper level of detail so I can be sure we really understand each other..." Things like this let you do a little management-education along the way.
3 - In general
I find that technical commmunication about uncertainty is always tricky - its case where everyone has to assume more than their fair share of communicating.
Another trick is enter a "can we fix this?" conversation that isn't loaded with the need to communicate about an actual task and estimate. Finding a low-stress time between tasks and booking in some time with your manager will let you say "hey, we seeem to have this bad cycle where I give you an estimate, you don't believe me, I can't change your mind, and I can't meet the deadline, so we are all screwed... how do we fix this?". Stepping up and engaing will show the boss that you really do care, you're not just blowing him off for fun... and it gives you both some space to think about the horrible pattern without the looming issue of the next task.
Also - I'm blithely assuming that everyone in your office has the same problem, or that there is no peer of yours who has a similar set of circumstances. The answers above are general guidelines for trying to figure out other people... mileage on any particular trick varies markedly on a manager by manager basis. People have all different sorts of styles and barriers to communication and sometimes the order of operations in a communication or other less-sensible sounding factors will come into play in terms of being effective. If you have a coworker who has similar needs to negotiate tasks with the boss, and he has better luck, ask for help. He likely has a few tricks to how to manage this... and if you're really stuck, ask him to help mediate - maybe he can be a translator between you and the boss and offer more tips at how to get through this...