I've had this too, however, I'm not convinced it's actually broken (as some have suggested) more in need of tweaking.
Playing a game as Hungary (I'm a masochist)... I've successfully sustained an alliance with France since the beginning of the game, fought many wars together, and they 'trust Hungary implicitly'. I'd had a similar thing with Muscovy; however, after Poland integrated Lithuania I supported Ukrainian rebels and they won. I guaranteed them, we married, and allied, then Muscovy (now Russia) broke the alliance and rivaled me.
The Muscovy situation is ok, it fits in the sense that here's a newly independent nation that I have supported right on it's borders, it's a threat as they have no idea what my intentions are. However, a year later, they unrival me, and want to be best friends again, they even make an alliance with Ukraine and we all fight together in a war against a newly independent Lithuania. Straight after the war, poof, rivaled again, I took no territory in this war.
I think the bigger issue here is the flip-flopping, why go from implicit trust to rival so quickly?
One thing I have noticed is that I have guaranteed France (so I get called in as they are usually fighting Austria, or Italian states which is good for me), I did not guarantee Muscovy. Am curious if there is some hidden modifier at play here?