The best way to do this it something like you've planned -
1. Add sprite to new collection
2. Find all tk2dBaseSprite derived objects, check the CurrentSprite, if matches the one we're changing, switch the collection and spriteId (SetSprite(collection, name))
3. Repeat for all scenes, and don't forget prefabs
4. Remove sprite form old collection.