Slower sql on 3.8.7

Hi;

apache / mod_perl 2 and mysql 5.1.24
Just upgraded to 3.8.7 including the database schema changes (changing
tables to utf8 – etc )

One of my users often executes the following query:
( Subject LIKE ‘EXAMPLE’ OR Subject LIKE ‘EXAMPLE CC’ OR Subject LIKE
‘EXAMPLE 2’ OR Requestor.EmailAddress LIKE ‘someemail.com’ ) AND (
Created > ‘31/12/08’ AND Created < ‘1/3/09’ )

Before the upgrade the page use to take ~ 1minute to display the result
, however since the upgrade its taking over 9 minutes;
the sql generated is
SELECT COUNT(DISTINCT main.id) FROM Tickets main CROSS JOIN Users
Users_3 JOIN Groups Groups_1 ON ( Groups_1.Domain = ‘RT::Ticket-Role’ )
AND ( Groups_1.Type = ‘Requestor’ ) AND ( Groups_1.Instance = main.id )
LEFT JOIN CachedGroupMembers CachedGroupMembers_2 ON (
CachedGroupMembers_2.MemberId = Users_3.id ) AND (
CachedGroupMembers_2.GroupId = Groups_1.id ) WHERE
(Users_3.EmailAddress LIKE ‘%someemail.com%’) AND (main.Status !=
‘deleted’) AND ( ( main.Subject LIKE ‘%EXAMPLE%’ OR main.Subject LIKE
‘%EXAMPLE CC%’ OR main.Subject LIKE ‘%EXAMPLE 2%’ OR (
CachedGroupMembers_2.id IS NOT NULL ) ) AND ( main.Created >
‘2008-12-31 00:00:00’ AND main.Created < ‘2009-03-01 00:00:00’ ) ) AND
(main.Type = ‘ticket’) AND (main.EffectiveId = main.id);

followed by:
SELECT (DISTINCT main.id) FROM Tickets main CROSS JOIN Users Users_3
JOIN Groups Groups_1 ON ( Groups_1.Domain = ‘RT::Ticket-Role’ ) AND (
Groups_1.Type = ‘Requestor’ ) AND ( Groups_1.Instance = main.id ) LEFT
JOIN CachedGroupMembers CachedGroupMembers_2 ON (
CachedGroupMembers_2.MemberId = Users_3.id ) AND (
CachedGroupMembers_2.GroupId = Groups_1.id ) WHERE
(Users_3.EmailAddress LIKE ‘%someemail.com%’) AND (main.Status !=
‘deleted’) AND ( ( main.Subject LIKE ‘%EXAMPLE%’ OR main.Subject LIKE
‘%EXAMPLE CC%’ OR main.Subject LIKE ‘%EXAMPLE 2%’ OR (
CachedGroupMembers_2.id IS NOT NULL ) ) AND ( main.Created >
‘2008-12-31 00:00:00’ AND main.Created < ‘2009-03-01 00:00:00’ ) ) AND
(main.Type = ‘ticket’) AND (main.EffectiveId = main.id);

An explain
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: Groups_1
type: ref
possible_keys: Groups1,Groups2,Group3,Group4,Group5
key: Groups2
key_len: 67
ref: const
rows: 166464
Extra: Using where; Using index
*************************** 2. row ***************************
id: 1
select_type: SIMPLE
table: Users_3
type: index
possible_keys: NULL
key: Users4
key_len: 123
ref: NULL
rows: 434757
Extra: Using where; Using index; Using join buffer
*************************** 3. row ***************************
id: 1
select_type: SIMPLE
table: main
type: eq_ref
possible_keys: PRIMARY,Tickets3,Tickets4,Tickets5,Tickets6
key: PRIMARY
key_len: 4
ref: rt3.Groups_1.Instance
rows: 1
Extra: Using where
*************************** 4. row ***************************
id: 1
select_type: SIMPLE
table: CachedGroupMembers_2
type: ref
possible_keys: DisGrouMem,GrouMem,CachedGroupMembers3
key: DisGrouMem
key_len: 10
ref: rt3.Groups_1.id,rt3.Users_3.id
rows: 1
Extra: Using where; Using index

Which to me looks fine, we do have a large database with 539049 tickets
and 2658347 rows in the Groups table and 5522188 in CachedGroupMembers ,
however I am puzzled why its x9 slower with the newer version ??
Have I missed an index ??

Any help will be truly appreciated.

Regards;