It’s up to the DM, but the language does not contain an explicit restriction.
The Changing a Skill section is actually quite short:
Sometimes you pick a skill proficiency that ends up not being very useful in the campaign or that no longer fits your character’s story. In those cases, talk to your DM about replacing that skill proficiency with another skill proficiency offered by your class at 1st level.
That this is entirely up to the DM is hard coded into this rule. That said, the language does not contain any restriction on which skills may be replaced, it simply says “sometimes you pick a skill”.
So this isn’t like an ability score improvement where I just pick what I want. I don’t have to talk to my DM when making a decision about an ability score improvement. Working with your DM on this is just part of the process.
Personally, I see no reason whatsoever to not allow you to change any skill proficiency you want. But your DM may see a reason, and that is okay too.
It should be noted that the Basic Rules encourage Customizing a Background:
To customize a background, you can replace one feature with any other one, choose any two skills, and choose a total of two tool proficiencies or languages from the sample backgrounds.
This further supports the idea that customizing your character is something that should be encouraged, including changing skills from your background.