Two parts: having them able to do it, and having the menu item. If you set links_minadminlevel to 1, and then send a level 1 user directly to /wp-admin/link-manager.php do they get in, with the ability to add a link? That works fine for me.
Then, to get the menu item, since it isn't looking at the options (yet, anyway), you're right that you have to edit menu.txt after saving a backup copy. Did you by any chance edit it in an editor that converts tabs to spaces, before? menu.php doesn't do much error trapping, and expects there to be a tab between the level and the filename, and the filename and the label, and if there was a space or spaces instead, it looks like bad things would probably happen. But without tabs-to-spaces, changing it to a 1 gave my test lowly luser a Links menu item.