My sweet tooth definitely changed - I used to do things like make a bowl of frosting and just eat it with a spoon. Cake was always a poor vehicle for straight frosting consumption. Super sweet coffee, constant candy eating - not surprisingly, I walked around dizzy and foggy most of the time, lol. I went cold turkey when I started eating primal and used some cheats for a while, i.e. adding Stevia to coffee and coconut oil fudge. Then. I stopped all of that for 30 days to see what happened. I can now eat 100% dark chocolate straight and ditched sweetener in my coffee altogether. I used to eat a lot of pineapple and that's almost unbearably sweet. I just eat pink grapefruit now, which tastes like tart candy.
I did have a couple of slips after Halloween and it all tasted disgusting. Waxy, gritty and sticky sweet. Wasn't hard to get back on the wagon after that. And yeah, I pick up natural sweetness in foods where I never noticed it before. This is one of things I am most happy about - sugar was a demon of mine for a long time.