When I visit Appearance → Menu, I can add custom links, but not any links I've already created under Links. How can I do this?
You can't add link/blogroll type items to the main navigation - add them as custom links instead.
To be more precise, you could do it, but you would need to write some code that hooked into the menu creation/editing section, present a list of blogroll links in a metabox, allowed you to choose from them, and then added these links to your menu. Seems easier to just add the ones you want as custom links.
Screen Options tab in the upper right corner of the UI, make sure all boxes are checked for everything you want visible- pages, posts, custom post types, taxonomies, etc..