What model of Plantronics do you currently have?
One possibility: Your new phone is paired but not connected because the headset is looking for the old phone. When powering on the headset it searches for the last connected cell phone. If the last connected phone is not within range, or the Bluetooth feature is turned off on the phone (which hopefully the first phone is turned off or at least out of range), then another phone within range that has been previously paired with the headset can be connected by tapping the Multi-function button.