SaltStack: [ERROR] The master key has changed and [CRITICAL] The Salt Master has rejected this minion's public key!

When the IP address of Salt master got changed and then a salt-minion started throwing the below error

[ERROR   ] The master key has changed, the salt master could have been subverted, verify salt master's public key
[CRITICAL] The Salt Master server's public key did not authenticate!
The master may need to be updated if it is a version of Salt lower than 2015.8.3, or
If you are confident that you are connecting to a valid Salt Master, then remove the master public key and restart the Salt Minion.
The master public key can be found at:
/etc/salt/pki/minion/minion_master.pub
Invalid master key



To get rid of this error, I ran below commands on troubled minion

• cd /etc/salt/pki/minion/
• mv minion_master.pub minion_master.pub.old
• mv minion.pem minion.pem.old
• mv minion.pub minion.pub.old
• salt-key --include-all --reject='ubuntu-14.04-amd64-vbox'         #on master
• service salt-minion restart
• salt-key --include-all --accept=ubuntu-14.04-amd64-vbox --yes      # on master
• service salt-master restart                    # on master

But this didn't help. The minion started throwing another error

root@ubuntu-14:/etc/salt/pki/minion# salt-call test.ping
[CRITICAL] The Salt Master has rejected this minion's public key!
To repair this issue, delete the public key for this minion on the Salt Master and restart this minion.
Or restart the Salt Master in open mode to clean out the keys. The Salt Minion will now exit.

To get rid of this error, I had to run

• salt-key --delete-all   # on master
• service salt-minion restart  # on all minions including master
• salt-key --accept-all