You may have created a paragraph style instead of a character style – the right-click option doesn't seem to give you the control you need.

Start by deleting the styles you made – sorry! press ctrl + shift + alt + s all at the same time to open the Styles list, locate a style you want to delete, click on the down arrow after the name and select Delete.

Next, select a block of coloured text again, the way you did the first time. This time, set up a new character style: click the New Style button bottom left of the Styles list, give the new style a name, and select Character from the style type pulldown.

Close the Styles list and try the find/replace trick again.