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.