Process Problems

While this won't be an issue for me much longer, I recently ran into a situation that I'm not sure how agile-ists handle during product/project development. I'll try to summarize what happened.

A project I was working is heading into its "maintenance" phase; essentially we completed Release 1 and are continuing to support the application as bugs and new features are found and requested by the customer. We sat down with the customer to prioritize what work should be done from their backlog for the first post-production iteration. At the time of meeting, there were still several (read, over 15) remaining outstanding/undelivered/unresolved/un-developed bugs that had not been tackled by the team. Now, my impression is that these bugs would be in the top of the stack/queue for work during the start of the coming iteration. However, the problem arose that it was the opinion - and rightfully so - that bugs should be addressed immediately once discovered.

Here's what I don't understand: the bugs will require us to investigate/triage/whatever to determine how much effort it will take (hours, days, etc.) to correct the problem. Obviously, the investigation is a non-trivial effort (read, legacy code). Given this information, where/when during our iteration(s) do we actually investigate the new bugs as the time to investigate is taken away from the development time we allotted for fixing bugs and/or implementing new features?

My initial thought was, "we'll have to do the estimates for the new ones at the end of the current iteration as part of our retrospective"; obviously that doesn't necessarily work because if we're on Day 2 of a 30-Day iteration, that leaves 28 or days before the customer sees any visible progress on the bug.

Not good.

So am I missing something here and making it too complicated? Obviously, the customer has stated that they want bugs fixed over new features. But it does feel that simple...or is it??