This thing just come to my notice that if you create N:N relationship on CRM 4.0 then other entities does not automatically gets displayed on Advanced find..
You need to go to particular entity and then you need to Change Display Option to either Use Plural Name or Use custom label..
if Display option is set to DO NOT DISPLAY then you these particular entity will not be available as Related Entity on Advanced Find Screen..
Again to understand all other aspects of Many to Many Relationship CRM 4.0, please refer to this article.
Hope this helps..