I assume you used the fuzzy select? It won't select the edge of things because they are a blend of the colors of the subject and the background. And if you increase the threshold the edges gets pixellated. To keep the smooth edges:
- Make sure you have an alpha channel: Layer>Transparency>Add alpha channel
- Make the background transparent:
- Fuzzy select the background (standard threshold)
- Select>Grow by two pixels, so that the selection covers the edge pixels
- Color>Color to alpha and remove the background color. The edge pixels will become partially transparent.
- Fuzzy select the background (standard threshold)
- Set the bucket-fill tool to Behind mode (this is the selector at the top of the Tool options), and bucket-fill the selection with the new color. The partially-transparent pixels will be partially painted, becoming a blend of the subject color and the new background color.