Slow Query Performance / SELECT DISTINCT w/COUNTs

[JP Howlett]

Hi, I have a query that is causing me some serious performance problems. It takes over 26 seconds to run. The problem exists on both my local test server and GoDaddy's server, so I don't think it's a problem with the server or hardware. The query is part of a series of queries used to create an interface that allows a user to build a mailing list from a table of about 100,000 records by selecting a state and then refining by county and city. This particular query, builds all the counties NOT currently in the selection for a given state -- the example below uses NJ.

Here is the query:
SELECT DISTINCT clients.county AS cn,
(SELECT COUNT(clients.id) FROM clients WHERE clients.state LIKE 'NJ' AND county LIKE cn ) AS cnt
FROM clients LEFT JOIN list_crit_county ON clients.county = list_crit_county.county
WHERE clients.state LIKE 'NJ' AND list_crit_county.county IS NULL ORDER BY cn ASC

I have indexes in the clients table on state, county, city, and I also have an index that is all 3 of those columns called refinecity (state, county, city).

The list_crit_county table is just a list of counties where the county name is the primary key (no other columns).

When I run the query with EXPLAIN, this is the output:
id select_type table type possible_keys key key_len ref rows Extra
1 PRIMARY clients range state,refinecity refinecity 2 NULL 3209 Using where; Using index; Using temporary; Using filesort
1 PRIMARY list_crit_county eq_ref PRIMARY PRIMARY 52 arnetdata.clients.county 1 Using where; Using index; Not exists; Distinct
2 DEPENDENT SUBQUERY clients range state,refinecity state 2 NULL 2688 Using where

Any help in figuring out how to optimize the query or table structure to improve performance would be much appreciated.

Thank you!