I don't think you'll really get anywhere without reworking the way things are done right now.
One example is that during development we only focus on new features
and ignore existing bugs and even introduce new bugs.
I am fairly certain that this is a grave mistake. Try to explain that bug fixing becomes more difficult and more expensive the longer it is postponed. I don't think there is any excuse for postponing bug fixes for so long.
All agile methods I know emphasize that the software should be technically ready to ship at the end of each cycle/iteration (or even continuously). That means any bug that you wouldn't want to ship must be fixed before any new features is started.
Try to work with people, and explain your concerns.
Finally, if you cannot get any kind of agreement on such basics, it may be best to move on.
Edit
Based on your amended question: I agree that bug fixing should be handled just like new features. I'd normally have single tasks for "small" bugs (up to a few hours) and stories with subtasks for "big" bugs (multiple days, possible to split into tasks). If your colleagues do not agree, point out that the advantages of agile methods apply to bug fixing just like to new features.
As to wheter to use an agile tracking tool or a bug database: Ideally, the two are integrated. If they are not, then yes, you'll have to track work in both. It's annoying, but I've done it myself, and didn't find it a big problem. You track bugs as usual, and just copy&paste the bug id into the title of a task/story when you schedule a bug to be worked on. The task is just a link to the bugtracker (eays if both are web-based), and all discussion is in the bug db. If you link consistenly, you could probably even run reports across both systems.
Finally, it you believe you cannot change the way development is organized, you'll have to work within these constraints. Things like introducing some agile methods into the bug fixing phase will probably help.
Still, I am convinced that splitting development into a "feature phase" and a "bugfixing phase" is a grave, possibly fatal mistake. It may not be so serious for your company (every situation is different), but if it is, and if your organization is unable to change this, then your organization may be so dysfunctional that you'd be better off elsewhere. But that is your call to make... good luck!
Edit 2
Finally, if company policies dictate "features first, bug fixing later", maybe you can sidestep them, e.g. by redefining bug fixes as new features (the difference is often a matter of opinion anyway). To some extent, you can try to introduce new ideas "from below" that way. You know, "if you can't beat them, join them".
I'm writing this from the perspective of Redmine. I haven't used Trac and only massaged the source with my eyes (not even reading it). At a high level, it appears to be similar to Redmine so many of the things that I say may apply to it too.
The first question that you need to look at is the integration between the bug tracking (and code change) side and the "customer facing" issue tracking. Different places may allow for a degree of openness that is not available in others.
- A closed-source software product certainly won't let the code changes get anywhere near the customer facing bug tracking system. The risk of having some code getting out is a worry for many of them.
- An open-source software product will often host the source code and bug tracking right alongside the customer issue tracking (they are one and the same). This can be seen in both Redmine and Trac.
- An academic setting... well, its probably somewhere in between.
That last point is key - is it a problem if the source gets out? Or for that matter, is it a problem if people see the discussion between developers of the product in the notes of an issue?
Redmine has the ability to restrict which certain users can read. You may have individual notes marked private or things such as "only people with the programmer role can see the repository."
If this is acceptable, the easiest thing is to integrate the end user issue tracking and bug tracking in the same system. You will likely want to separate "bugs" and "issues" from each other, though note that there is a relationship between them. An end user issue may be caused by a bug, or it may be something the end user doesn't understand.
Issues and bugs have different work flows - issues may go through something like "new -> confirmed -> waiting for fix -> resolved" while a bug may go through "new -> assigned -> working -> code review -> working -> code review -> deployed -> closed" or something like that. There are likely as many work flows as there are installations. Having a "blocked by" relationship from the issue to the bug allows you to easily relate the two systems together.
All of that was assuming that it was acceptable to have one system host both, you will then find yourself with two different systems - one that is customer facing, one that is developer facing. This may involve a bit more work - somehow, someone needs to bridge the gap between the two - developers need to be aware of bugs that are discovered by the end user in their bug tracking system.
I haven't found a modern bug tracking system that plays nicely with others. Everything tries to be self contained and when commercial products have bug tracking systems, they make it so that it's easy to migrate to it and use everything within its own product line. You may find an API that lets you do some things, but for the most part - nope.
The question here becomes what is the workload and how does one want to integrate the two (picture two spoiled children sitting with their backs to each other not wanting to play)? Is it enough just to have a link from one system to the other? Is the amount of new issues low enough that this can be done by hand? or will you need to start exploring some way to poll from one and update the other?
Make sure that when integrating the two systems that you use the API rather than trying to go behind its back and tinker with the database with updates directly. There are dangers to that - the table structure of modern bug trackers is a big large and they are managed in the application. Going behind the back of the application may cause issues with data integrity. As mentioned before, instead of updating and inserting at the database, use the public API for the application (Redmine's API for issues for example).
The extent of the business logic and the integration points are something that needs to be examined before jumping off and doing it. Which way does the data flow (both ways gets very interesting at times) and what data flows. Are you copying issues into bugs once they reach a certain state? How do you keep track to make sure you don't create the same issue again and again (need to update the data model of the bug tracking system)? What happens when an issue is marked as closed in a bug tracking system - does that flow back?
All in all, its probably simplest to try to use the same system and manage the permissions / customize it so that it works the way you want it to if it is not critically bad if some bit of knowledge from the developers leaks out.
Best Answer
"...finds a bug, the report goes into a bug tracking database and also becomes a story which should be prioritized just like all other work.
The question is, should bug tracking and feature tracking be different, and can you use a single system to do both as well as schedule iterations/milestones/etc...
In terms of a "pure" Agile approach, you allow your team to use any combination of tools and processes that works well for them. Sure, you may find a single product that does everything, but perhaps it doesn't do some things as well as you'd like. If you run multiple systems, you need to determine just how integrated they need to be, and if any integration is needed, find the means to do it, and decide just how much information needs to be duplicated. It all boils down to a cost/benefit situation, so naturally any system employed needs to take into account the impact on a team's overall efficiency.
Where I work, we use a Redmine system to track bugs and features in a single system for multiple projects, with links between each project where dependencies exist. We create labels that relate to milestones, which for us are effectively long iterations that may range anywhere from a matter of weeks to a matter of months. For individual tasks and features, we tend not to track iterations too closely, so we have no need to worry about burn-down charts, white boards, sticky notes, feature cards and all of that stuff, as we've found that for our specific needs, some of this stuff is overkill. Each feature itself effectively represents small iterations of between 2-10 days duration, and for those that might care, we log our estimates of time versus actual time for later analysis. This may sound a little ad-hoc, but works for us and ultimately our real measure is working code within a series of time frames.
I suppose if we decided to employ another more formally "regimented" methodology, we might consider a tool to aid in tracking progress, but with what we currently have invested in our present method, we'd probably feed at a minimum the short feature descriptions and time data to another system, unless someone has developed a module for Redmine that does what we want it to, or if it became really important to us, we might create the Redmine module ourselves to avoid any nasty integration headaches that might concern us.