解決方法
ポリシードキュメントを直接編集して、principalにARNでない何かが混じっていたら削除する 
https://docs.aws.amazon.com/ja_jp/IAM/latest/UserGuide/reference_policies_elements_principal.html
状況
- 暗号化キーの利用ポリシーに数名のIAMアカウントを指定していた
- チーム編成に伴い、上記ポリシーから一部IAMアカウントを削除した
- チーム編成に伴い、上記ポリシーに新規IAMアカウントを追加しようとした
調べてわかったことですが、IAMアカウントを削除した場合、
ポリシーに指定されていたIAMアカウントARNは別の文字列に置き換えられるようです。
今回は削除したIAMアカウントの定義が残ったまま、
新規IAMアカウントを追加して利用ポリシーを更新しようとしたので
Policy contains a statement with one or more invalid principals.
というエラーになったと思われます。
上記削除ずみのアカウントのprincipalを削除することで、追加のpolicy変更ができるようになりました 