CRM 2011: The Relationship with name = was not found in the MetadataCache - N:N relationship

Error:

The Relationship with name = <relationship_name> was not found in the MetadataCache.
 If you encounter this error while dealing with N:N native relationship in CRM 2011 (especially in custom code), first thing you might want to check is the N:N native relationship itself.

When we create a native N:N relationship between the two entities, upon selecting entities CRM itself populates the following fields with the same value

• Name (maximum 45 characters allowed, including "new_")
• Relationship Entity Name (maximum 43 characters allowed, "including new_")

for some reason the "Name" field is limited to have maximum of 45 characters and
"Relationship Entity Name" is limited to have maximum of 43 characters.

so if the schema names of the entities are long enough to exceed the limit then extra characters will be truncated to be different because of different lengths allowed.

Solution:

Delete the existing N:N relationship and create a new one with shorter values in "Name" and "Relationship Entity Name" fields.
I entered the same values because i don't think it matters. You can try with different values, I think the key is to have shorter values.