I have changed my Google+ photo 6 months ago. I even removed my old photo from the list of profile photos to be sure the old photo is gone.
I even changed my photo in Gmail → Settings → My picture.
The Gmail photo on my phone hasn't changed even now. When I call people with smartphones, they see my old photo on the screen. On the mobile Gmail app I see my old Gmail photo next to my emails.
Best Answer
Is the clue in "When I call people with smartphones, they see my old photo on the screen."
When you call me, I expect my phone to show me the picture of you from my contacts book, not from your profile. Granted, when I set you up in my contacts the first time, it's possible that the initial values were taken from your Google profile. But after that, I'd expect updates to my data about you only when I choose, not when you do.