I wasn't primal when I went to basic training, but I did notice that I could no longer drink juice, as the sugar would give me a stomach ache.
Your body will adjust as best it can to whatever you throw at it. You do not want to be the guy in training who has a special diet, unless you really need one. After you finish your training you will be able to control what you eat a lot better, typically.
I've been in the Army for over 11 years. PM me if you have any specific questions.