You need to do Object > Expand to turn the Live Paint object into ordinary filled objects before you can use Select > Same.
Note that this can't be reversed, so if you still want to keep the Live Paint object, make a copy of it before expanding.
Live Paint is somewhat like an effect. You can see this if you open up the Appearance panel, and just like other effects in Illustrator, they don't become real objects until expanded. That's why you can't use all the selection tools on parts within the Live Paint object until they're expanded to make real objects.
There is another way to work with Live Paint so that you don't encounter this problem, and it's possible to avoid the need to expand it. You can create global colour swatches, and use these to fill your Live Paint artwork. Then you could edit the global colour swatch, and all instances of it will automatically update. This is perhaps something to remember for future projects, since it's probably too late to do this now you've already made the artwork.