You’re still gaining reputation with them, but it takes multiple gifts to unlock a new star level. For example, suppose you gain a star every 10 reputation you have with a character, but a gift only adds 3 reputation. (I don’t remember the exact numbers.) How much a character likes the gift you’ve given them also effects how much reputation you earn with them.