I understand that if we are changing an existing fee on our fee schedule that we must notify all customers 30 days before the change; however, if we want to add a new fee to the schedule, do we also have to give the same notification?

Yes. You are making a change to the fee schedule by adding a new fee so advance notification is required.