Some relationship types have a restriction on the role level. You can check that under Manage > Relationships types > objects x occurrences > your type. Does it have any "left" or "right" side restrictions?
@juliaweist No, left and right restrictions are set NONE right now...
Ok, just making sure I understand the issue: you're able to create a relationship between objects and occurrences from the Object UI, but you don't see the link from the Occurrence UI? Can you upload screenshots of everything? The relationship fields on both UIs and the UI restrictions for both?