Being a freelance developer for the last 10 years or so, I have seen and used almost every project management software you can think of, open-source and closed, and I have found that the "best bug tracking tool" completely depends on your process. I employ and direct teams in an Agile process that involves loose story-based requirements with point-based estimates, two-week cycles of iterative development, planning and retrospective sessions, and look-ahead and show-and-tell meetings with the stakeholders. It's important to me, then, that my tools have a method of capturing all those pieces with as much detail as I need but no more.
On projects, I've successfully used Pivotal Tracker, Unfuddle, Redmine, Codebase HQ, Basecamp, Trello, and many others. I usually recommend people to Trello for light, agile management; it's essentially a digitized version of sticky notes and swim lanes. If your team actually needs a full-featured ticketing system, see Redmine (Rails), Trac (Python), or Mantis (PHP), depending on your language preference. Hosting a version of these yourself is fairly trivial, and numerous options exist for cheap or free hosted versions. For something in the middle, Github Issues is a good fit and the open-source clone GitLab.org replicates most of those features nicely.
However, if you're looking for a hosted version, you're probably looking to offload that tricky "backup" thingy, and in that case, how important is your data? How proprietary? What's your business model? If you're working on an open-source project, Github will give your team a free account with private repos, issues, wikis, and the like. If you're okay with your project being "readable by all", public projects on Pivotal are still free.
I'm mostly a consultant these days, leading small groups of junior or intermediate developers into a more productive, more mature, fully operational teams of senior software developers. One of the first things I teach folks is how to use a project management system... and why! It'll save your bacon if it's simple, effective, and reliable. With a few minutes of discussion about your project, I can probably help you select the right tool and service for your team. Let me know if I can help with that. Best of luck!
David hit the nail on the head. I have managed software teams on several occasions. I've been exposed to a good number of systems. The one I personally enjoyed is redmine. As a manager, it gave me quick and thorough information and visibility into daily production.
This answer is more of a testimonial. If you want more specific advice, I would definitely call David. He sounds like he can really help you.
P.s. Atlassian also offers hosted and self-hosted products with support. We started with them but once we hit the limit of 10 users, the price jumps significantly. That is when we switched to self-hosted Redmine. FYI
Answering by saying that it's too difficult to answer....bah humbug.
Try something Kanban style first (like Trello). If that doesn't work, slowly work your way up in complexity.
The truth is...no one ever likes what you pick. But once it is adopted, people will stop complaining.
A great way to do it from a management perspective is to pick a solution and go with it. Then when everyone starts complaining ask what they would rather have...let the group come to consensus and then choose that.
Or call me up and we can talk for 10 hours about all the pros and cons of every tracker software out there. I'd be happy to do it - cheers buddy.
Mantis is pretty sweet...ahem.
The solution for your team largely depends on your team and tools that you are currently using. If your team is already using github, then github issues might be the simplest tool to use in your work flow. There are other bug tracking software that can plug directly into github issues.