You may have a group of contacts for whom you have missed ticking their contact preferences for Email.
You tried an "Update Many Contacts" on that group, ticked the box on the left for Contact Preferences: Email but it had made no difference and you still can't select that group of contacts for your email campaign.
Not to worry, help is at hand!
A: Re-work your Update Many Contacts but this time not only tick the box on the left but also tick the Yes radio button on the right:
That should sort it