I believe this is closely related with the fact that many traits in EB cause minus Command points. Check your dudes' traits. I'm pretty sure they have enough Command boosting ones, as well as negative. I didn't like this as well, so I installed the "Command Stars and Corsus Honorum" minimod located at the Unofficial Modding Projects Section.

Maion