We've had good results with FogBugz. We are a group of eight developers and user support staff in a company of 300, and it's the right size for us. We have a bit under 15,000 cases in the system, going back to June 2006, so I can't say we're stressing the system. I don't know how it would scale.
I used Trac briefly about four years ago and liked it, but it was a bit of a bear to install. On the other hand, you spend the majority of your time using a system, not installing it. Once installed it was fine. I liked the front-end to Subversion a lot, and the integrated wiki was a huge plus. It's written in Python, but there was a time when the Ruby developers used it, although they moved to Redmine a while ago.
I hear good things about Redmine. Sounds like Trac, but improved. I'm planning on experimenting with it.
We used Basecamp a couple of years ago to plan a major overhaul of our flagship web site, and it was a good fit. But we maintain the web site with FogBugz, which we feel is a better fit for development and maintenance as opposed to project planning.
I would no longer choose to work with any sort of tracking system that didn't have an integrated wiki that gave you easy cross-linking between wiki pages and cases or tickets.