Appearance > Menus not reflecting permalinks custom structure

I’ve edited my permalink structure to appear as /%category%/%postname%/ so that the word “category” doesn’t appear in my URL. I’ve two custom menus set up and I’ve dragged items from the Categories box into my menus.

When I call my menus with <?php wp_nav_menu(array('theme_location' => 'secondary'));?> the URLs appear as “http://mysite.com/category/fruits/apples” instead of “http://mysite.com/fruits/apples” which I specified. Typing in fruits/apples works fine; I just can’t get Appearance > menus to reflect my custom permalink structure.

Does having custom permalink structures mean I have to create custom links for every page in Appearance > Menus or am I missing something?