Recently, I had to upgrade a redmine setup. Amongst other requirements evolutions, which were handled fine by 'aptitude' and 'gem install', I found out I had to manually install a 'mysql' gem, presumably because it was not included any more with one of the dependency shipped with redmine build.
For what is worth, this is rails-related : the mysql connector is no more included, you have to install it separately. The redmine documentation went pretty clear to that point, telling me to run a classic "gem install mysql".