I could be wrong on this, but I don't believe associations can be searched since they're not indexable into Lucene (so even if you could get them to show up on the advanced search page, users still wouldn't be able to search by them). You might be able to use a property of type NodeRef instead (since I believe NodeRefs can be indexed), although the default property sheet widget for NodeRefs is different than it is for associations.
Hopefully someone a bit more knowledgeable than I can chime in and set us both straight. :wink:
Cheers,
Peter