I currently am a user from Paint.Net and generally use it to do basic image manipulations. One of my main tasks to to take an object and convert it to show what it might look like in a different color. I have had good success with this in Paint.Net using the recolor tool. The increased ease of the selection in Krita seems appealing, but I haven't figured out a way to do easy recolor.

Any suggestions?

There's several ways to do recoloring. Can you show/link an example of previous work, then I can suggest the one that gives the closest results.