The Add Media button isn't for adding links.
To add a link in the visual editor, select the text you want to be the link text and click the link button in the toolbar. It looks like 2 loops of a chain joined together. That should be the one you've been using.
It'll ask you for URL and title and the button says 'Add Link'. If you've done this successfully, the text should turn blue. You won't be able to follow the link in the editor, but once you publish the post, the link shows up.
If the above still doesn't work, perhaps your theme or a plugin is causing a conflict.