役員の変更登記を行う必要があります。
履歴事項全部証明書は何も変わっていないとのことですが、それは変更登記を行っていないからだと思います。
変更登記は、法人事務所の所在地を所管する法務局あるいはその出張所で行います。登記手続きの詳細は実際に手続きを行う法務局や出張所にお尋ねされるのが間違いないと思います。法務局のホームページでは申請書類の記載例などを示していますので、事前にそれを確認されると参考になると思います。
NPO法人役員変更登記申請書(理事全員重任)記載例(PDFファイル)
http://www.moj.go.jp/ONLINE/COMMERCE/k11-1-19.pdf※ 登記に必要な書類も、この記載例に示されています。
手続きの大まかな流れとしては、以下のようになると思います。
1)総会での役員選任(再任)の決議
2)総会議事録の作成と、再任された理事による就任承諾書及び宣誓書の作成
3)役員の変更(全員重任)の登記
4)所轄庁への役員変更届の提出
ちなみに、3)→4)の流れは4)→3)になっても法的な問題はないと思います。所轄庁が3)→4)の順を示すのは、登記した内容が正確に反映された役員変更届を欲しているからだと思いますが。
また、登記の対象となる役員は理事のみですが、所轄庁に提出する役員変更届への記載対象は理事だけではなく監事も含めますのでご注意ください。