Hard to tell from your question, but I'm guessing your customers table will look something like:
id fName lName deleted
---------------------------------
1 John Doe N
2 Bill Clinton N
3 Fred Smith N
4 George Bush Y
Your query, as you've stated it in your question, will never work, as it will look like this:
SELECT *
FROM customer
WHERE fname LIKE '%Bill Clinton%' AND deleted = 'N'
OR
lName LIKE '%Bill Clinton%' AND deleted = 'N'
There are no records in the table where the fName OR lName fields contain "Bill Clinton"
You would have to massage your #attributes.q# text so it'll generate something like this:
SELECT *
FROM customer
WHERE ((fName LIKE '%Bill%') OR (fName LIKE '%Clinton%')) AND deleted = 'N'
OR
((lName LIKE '%Bill%') etc.....
LIKE comparisons are very much like using wildcards in filenames. They won't split up a block of text for you, but will tell you if a chunk of text exists, verbatim, inside another chunk of text.
I think what you need is a FULLTEXT search, which will consider individual words in a query string and return results. Of course, FULLTEXT is only available on MyISAM table types, so if you're using InnoDB or some other type, you're out of luck.