Users are unable to approve a one way relationship
It looks like this actually was a permissions issue. In order for someone to be able to accept a relationship request, they also need permission to make the request. 

In order to accomplish what I needed I also had to enable the "User Relationship Implications" module.