I think they definitely impact cravings, and that's why it can take time for people to adjust to a new diet. Like getting away from a lot of sugar (SAD to paleo/primal), your gut is still used to a much higher fiber and sugar intake, so it will take some time for the flora to adapt and stop giving you cravings for sweets. For some people, those cravings may be indicators of missing nutrients (I crave ice cream when I need to up fat, oranges when I'm sick), but for others, it may just be "habit" from poor nutrition prior to the change. Since this is all established as soon as we are out of the womb, it can be very hard to change these cravings or get rid of them. But everybody's adaption period is different.