Do I need to get a new AFSP approval if I change to a new part 61 instructor?
Yes, you will need to apply for AFSP approval for your new training provider. The Application Guide for the AFSP says in step 7:


  It is possible for a Candidate to have several active training requests at a given time. These requests may be for the same or different flight training providers. Each training request form will be processed separately; AFSP approval is valid only for the Provider listed in the application.


So if you needed AFSP approval for your original training provider, you will need a new approval to switch to a different provider.