How to create a custom menu in Drupal 7?
Step 1: Create the menu

Navigate to admin/structure/menu/add in your site and add the menu you want. Add at least the "Title" of the menu (like Custom menu), save it, and it will show up in admin/structure/menu also. From there you can start to add menu items (which will be the "new links" you are looking for).

Step 2: Make the menu visible

Head over to admin/structure/block to indicate in which region of your theme you want that newly added menu (Custom menu) to be shown.

Step 3: Clear the cache

And don't forget to clear the cache (since you're changing things that are cache sensitive ...). I think "menu" cache should be sufficient, but to be sure I usually just clear all caches ...