Bootstrap te crea por defecto los "márgenes" (pongo entre comillas porque no son márgenes) con 15px de padding en las columnas. Al rellenar la columna de color se te colorea toda la columna.
Prueba a incluir un div dentro del col-md-loquesea y dale a este div el color.
Algo así:
Código HTML:
Ver original <div style="background:#f00">col con fondo rojo
</div> <div style="background:#069">col con fondo azul
</div>
Saludos