Problem When Adding a Category to an Existing post

Here’s my permalink structure: /%category%/%postname%/

If I edit an existing post:

http://www.abc.com/blah-category/this-blah-story/

and I add another category, so now the post is in Blah Category and Blah 2 Category

much to my surprise after I add the new category and press Save, the url to the story becomes:

http://www.abc.com/blah-2-category/this-blah-story/

which will break any incoming links or trackbacks to the story.

Note: I didn’t remove the primary category, only added another one.

Is this a bug, or did I do something wrong?

Thanks for the help,

JS