Isn't a relate just a relate. Sounds like you need to create a relationship instead. You can't join data using a predefined relationship class if one doesn't exist and a relate isn't a relationship class. You create a relationship class through Arc Catalog. You can do this through the Arc Catalog tab within ArcGIS 10 as long as you don't have an edit session started.
Once you have the relationship class you can use the Join data based on existing relationship class in the join dialog. I suspect the reason you aren't seeing this option is because there are no relationship classes on the layer you're trying to join.