This is the correct answer and the problem actually lies in a fluke with the SRP/CAL exchange when BES checks in with RIM's infrastructure. The SRP will identify what type of BES you have installed and what type of CAL's are active on it.
If you look at your keys the differences between versions will be obvious.
When "upgrading" from any limited version to Enterprise, the full installer attempts to recognize the keys and authenticate them as Enterprise keys - half of the time the change is not applied correctly (to all) CAL's - at this point, the BES will continue to function, but you will get persistent "out of CAL's" warnings when attempting to add new users.