Scenario
When accessing a Vendor Record, a custom role is unable to add relationships using the Other Relationship option on the record.
Solution
1. Navigate to Setup > Users/Roles > Manage Roles.
2. Edit Custom Role in question.
2. Under the Lists subtab of the Permissions tab, add Companies.
3. Set Access Level to at least Edit.
4. Save.