Have a solution!
Change your AppleID password (either at applied.apple.com or in iTunes).
You'll then need to sign back in on each of your devices and Macs (or sign out and back in if it doesn't ask you. I then had to restart my mac, and it now only shows the devices I have signed back in on...so removing my old phone.
Hope this works for you!