Tying backgrounds to both starter feats and stat bumps seems a bit restrictive. They either need more backgrounds (and thus more stat bump feat combos) or they need to give alternates in the background block.
For instance, Soldier could give +2 str/+1 con OR +2 dex/+1 con and then for feat savage attacker OR tough. This would give more customization choices, and would not force you to such a narrow set of background choices.
