The order of where clauses might have an impact. SQL Server processes multiple WHERE clauses separated by Ands from Left to Right. Put the clauses which reference indexed fields before clauses which do not. That way, the substring clauses (which aren't indexed) won't be run as many times. Within a class (indexed or non-indexed,) place the clauses which most greatly restrict the data set first. This serves to most greatly reduce the number of records for any subsequent clauses. (Oracle is the reverse of this, BTW)
If you don't actually need the DISTINCT clause, don't use it.
If all else fails, You may have to increase the value of the connection CommandTimeout property.
"Lisa, in this house, we obey the laws of thermodynamics!" - Homer Simpson
"I have my standards. They may be low, but I have them!" - Bette Middler
"It's a book about a Spanish guy named Manual. You should read it." - Dilbert