MySQL COUNT Query taking too long time to execute
There are three aspects you need to rework
ASPECT #1 : THE QUERY
Please look at the Query
SELECT COUNT(*) AS `count`
FROM `yuldi`.`businesses` AS `Business`
LEFT JOIN `yuldi`.`businesses_categories` AS `BusinessesCategory`
    ON (`Business`.`id` = `BusinessesCategory`.`business_id`)
LEFT JOIN `yuldi`.`categories` AS `Category`
    ON (`BusinessesCategory`.`category_id` = `Category`.`id`)
WHERE `Category`.`slug` = 'building-construction';

You are doing LEFT JOINs. That is not necessary for doing a COUNT. Why ?
If you are counting the number of businesses, you only need to count from one table
SELECT COUNT(*) AS `count`
FROM `yuldi`.`businesses` AS `Business`;

Since you have a WHERE clause on Category.slug, the JOINs are needed. You should switch from LEFT JOINs to INNER JOINs. That will produce a smaller internal temp table. That temp table will be searched for the slug 'building-construction'.
ASPECT #2 : INDEXES
From the EXPLAIN plan, I see two indexes similarly named

fk_businesses_has_categories_categories1_idx
fk_businesses_has_categories_businesses_idx

You need to look at the columns for them and make sure the column lists are not identical.
You may want to make two indexes
ALTER TABLE BusinessesCategory
    ADD INDEX bus_cat_ndx (business_id,category_id),
    ADD INDEX cat_bus_ndx (category_id,business_id)
;

Having compound indexes could mean less culling through tables for JOIN information.
Keep in mind, this suggestion is a blind one since I do not know the key distribution of your data.
ASPECT #3 : CACHING
Gathering index statistics is the sake of query evaluation does not immediately translate into a slow query. That slowness is manifested by the real culprit : CACHING. The reason your query runs faster the second time around has to do with the data you read the first time. The data you needed was most likely not available in MySQL's caches when you issued the query.
The two main caches for MySQL are the InnoDB Buffer Pool (for queries hitting InnoDB tables) and the MyISAM key cache (for queries hitting MyISAM tables).
InnoDB caches data and index pages, while MyISAM caches only index pages.
When retrieving data for comparison, mysqld tries to determine if the data it needs is in RAM first. There are server status variables to monitor for this:
InnoDB Caching

Innodb_buffer_pool_read_requests : The number of logical read requests.
Innodb_buffer_pool_reads : The number of logical reads that InnoDB could not satisfy from the buffer pool, and had to read directly from disk.

MyISAM Caching

Key_read_requests : The number of requests to read a key block from the MyISAM key cache.
Key_reads : The number of physical reads of a key block from disk into the MyISAM key cache. If Key_reads is large, then your key_buffer_size value is probably too small. The cache miss rate can be calculated as Key_reads/Key_read_requests.

If your query was slow the first time, it simply means the data you need for the query was not in a cache. This would have been indicated by either your Innodb_buffer_pool_reads or Key_reads incrementing.
The second time, your data and/or index pages for the same query would be in RAM and more available for your queries and queries from others.
I suggest you look over the sizes of your InnoDB Buffer Pool and/or MyISAM key cache.