Select the text box and choose"Text Frame Options" under Object (or Command B) and change your gutter setting there.
The question is, "where did you make the gutter to small?" On pagelevel. This means you see the purple margin/gutter lines moving on change, but the text will stay in place. You can change this in Layout >> Margins and Columns. Make sure you have the preview box checked.
If this is the case, you can then, manually change the width of your textframes to get them right, or use the 'Layout adjustment' as described by Scott. You will see your text reflow.
Or you have set the gutter on your text-frame. In this case, click the frame to select it, type cmd/ctrl-B (textframe options) and adjust the gutter. Make sure you have the preview box checked.
When working with Master pages, make sure you make the adjustment on the master-page.
I am having the same issue as the first post here [I have InDesign 6 so there are some variations as well]. I have a 478 page document ready to get a proof printed but I keep getting this error from the printer:
" The interior doesn't have sufficient margins for printing. For a book with  pages, the gutter (inside) margin requirement is 0.88".
The gutter is presently set to .423 and I figure that means I need to make it .44 so that it totals .88
when I do Control B, it makes me have to manually change each pages gutter.
when I go to layout > margins it says gutter .44 and adjust page settings is selected but nothing changes on the pages and when I do control B on a page it still needs to be manually changed (at which time I do not see any visual changes). ???
There should be a way to do this globally, ey.
First, I think they mean .88, not .44 per page.
Second, make your adjustment on the master page.
I have this same issue (CS6). I am creating a new document, and adjusting the gutter doesn't seem to alter the page layout on the screen, whether I do it in the New Document window, or in the Layout > Margins and Columns window of the Master Page (yes, I have Preview selected).
In Indesign Gutter means space between columns. Does you document have more than one column?
If InDesign gutter means the space between columns, how do I set a book's gutter (inside page margin).
If you check "Facing pages" when setting up your document, you'll have the option to set the inside margin.
And if you need to change it in an existing file you can do it from Layout > Margins and Columns...