Your problem is here:
This is a cross join effect and will result in your query having to check every row for HB for each new row of All_Members.
FROM All_Members, HB
WHERE All_Members.Email != HB.EmailHB
so if All_members has 1000 rows and HB has 1000 rows then your cross join will have an effect of looking through 1 million rows.
You want this instead:
One other note, is that DISTINCT works on all columns in your select statement. So if you have two rows with the same Title, Firstname and Lastname but two different email addresses, both rows are returned.
SELECT DISTINCT `Email` , `Title` , `FirstName` , `LastName`
All_Members.Email NOT IN
(SELECT HB.EmailHB FROM HB)
AND `ENewsletter` = 'y'
AND `Email` != '' ''
That is most likely what you want, but just pointing out that distinct does not work on just the one column.