Apparently Select2 (http://ivaynberg.github.io/select2/) is a solution to putting icons in option tags. However, perhaps due to my lack of knowledge, I just couldn't make it work. In the end I resorted to using lists (I was also using Bootstrap)
<a class="btn dropdown-toggle category" data-toggle="dropdown" href="#">All Categories <span class="caret pull-right"></span></a>
<ul id="category" class="dropdown-menu">
<li><a href="#"><i class="icon"></i> Category A</a></li>
<li><a href="#"><i class="icon"></i> Category B</a></li>
..
</ul>
There is a drawback though, the id of the list has to be unique. So, if like me you had 5 different lists in one page, you have to declare (?) all of them in javascript making the codes chunky.
$(function(){
$("#category li a").click(function(){
$(".category").val($(this).text());
});
});
Hope that help shed some light.