Why is this query sometimes slow, and what can I do to make it faster?
Most likely, the EXPLAIN plan is probably stating that the query will perform an index merge. That's when two indexes are searched and the intersection between them yields the results.
SUGGESTION
You can probably achieve slight better performance by creating one index as follows:
ALTER TABLE logs ADD INDEX (deployment_id,type,received_at,time_slice);

This will read from the index only to generate results. It should not have to read from the table. The reason ? Every column in the query is in the index.
TRADEOFF
This will make the table bigger but can improve read speed.
If the performance is the same after creating the index, you can probably do without the index at this time.
GIVE IT A TRY !!!