I have several users who have permissions to create, edit, and link issues but somehow can't add epic links to an issue (either an existing issue, or at creation time). They can remove epic links from existing issues. This is a new problem and I'm not sure what could have changed to cause it... they were previously able to create and modify epic links, now they can only remove epic links. There is no indication of failure, it just silently ignores that an epic is selected. If editing an existing issue, and all they do is try to add an epic link, nothing even shows up in the activity stream.
I'm running JIRA Software 7.5, these particular users are JIRA Core users (and always have been), but I don't think it's related to JIRA Core vs JIRA Software license because I gave one user Software application access and it still didn't work. With my admin account, I am able to add/change epic links on issues (if I give the admin group all permissions on the project, which I did just for testing).
The only recent modifications that have been made were on workflows, but I can't see how that would affect epic links.