Permalinks Grab Categories Alphabetical. How To Fix?

For some reason anytime I publish a post and select the categories to have this post in, the permalinks change to the first category name. For instance, I have Apple, Banana, Carrot and Grapes for categories. I would like the permalink to be http//…/banana/how-to-eat/ (the structure I’m using /%category%/%postname%/) So I check banana and post. The permalink is correct. BUT now I go to edit the post because for some reason I want it to be in the “Apple” category as well, I click Apple and hit edit, the permalink is now http//…/apple/how-to-eat/

No matter what I do, if I change the category, it always changes the permalink to the latest alphabetical letter in the categories.

How can I fix this? I never did it before and the permalink stayed the same when editing or selecting more than one category.