Tracker:
http://joomlacode.org/gf/project/joomla/tracker/?action=TrackerItemEdit&tracker_id=8549&tracker_item_id=30242

According to Elin suggestion I have added a field in "tag configuration" that allows you to define the classes for the tag link:

Comments?

I forgot to mention, right now the feature adds "label label-info" by default in case you don't fill with any other class in the configuration.

TESTING INSTRUCTIONS:
1.- Install a Joomla 3.1 and add this patch
https://github.com/joomla/joomla-cms/pull/777.diff
2.- Go to an article and add some tags
3.- Go to the frontend view of the article. You should see the tags inside a
"blue pill" format.
4.- Go to TAGs Component, enter in the a tag linked in the article and go to
"options"->CSS Class for tag link. Add any text to this textfield,
for instance add "label label-warning". Click SAVE
5.- Go to the frontend and check the article, the tag thad you changed should
look different.

Thanks for testing ^_^

I would recommend you add the default="label label-info" to the xml field too.
So people know what they are replacing when they enter something.

Added @nonumber suggestion and committed at f322969