I believe you need to have 5 regional barracks, not the native barracks that you would build in your homeland provinces but your allied state ones.