Steve,
It is possible you have not set these properties in Microsoft Commerce Server Catalog and Inventory Schema manager properly. You must set the "Free Text Searchable" property to true for any property that is custom.
See the documentation here:
http://msdn.microsoft.com/en-us/library/ms943113(v=cs.70).aspx
As stated in the documentation for the Free Text Searchable property:
"Select this check box so that free text searching on the catalog will apply to values stored in this property.
When you select Free Text Searchable, Commerce Server adds the property definition to the full-text index for the catalog. You must update the full-text index after changing items in the catalogs that are marked as searchable."
IMPORTANT NOTE: Make sure to update the full text index, otherwise the Catalog Web Service will be querying an index that is not populated, even if you have set the "Free Text Searchable" property to true, you still have to update the index.