I have yet to find a definitive answer to this question. Right now this does not work for me in sharepoint 2007 and the only common characteristic I can find for the fields is that they are calculated fields.
A full crawl has been performed and the calculated fields show up. Managed properties have been added and the advanced search web parts properly modified to allow search on the properties. All other (non-calculated) fields added to the managed properties and search work fine.
The Calculated fields are text fields with the formula "=LEFT([field name],2)". The reference field is a choice field.
Anyone? If search on calculated fields is not supported, I really just need to get back to the user to say "Nope, it can't be done."