I used to have problems updating images after image styles were changed. Images would remain the same size they were before the style updates. Then I realized the problem was with my template files. I used to have static references to images, in the styles directories, which was wrong.
Then I realized I should use a function to display those images. This is how I do it now:
<img src="<?php print image_style_url('large', $node->field_image[$node->language][0]['uri']) ?>" />
The 'large' attribute is the image style name, you can use 'medium', 'thumbnail' or whatever custom style you have defined.
This solved the problem for me. When displayed, images appear according to the latest definition I have applied.
I don't know how Colorbox handles images with styles. Anyway, I hope my answer helps you.