Indexed but still slow during query
first what You need, check explain plan of query:

EXPLAIN SELECT *
FROM
   ws_call_logs
WHERE
   (corr_id is not null
      AND http_status_code &gt; 200
      AND created_timestamp &gt;= '2015-11-01 23:00:00'  
      AND created_timestamp &lt;= '2015-11-30 23:00:00'
   ) 
ORDER BY
   created_timestamp
DESC LIMIT 25;


It return You information about which indexes from present MySQL will use when run query

Than You will check cardinality of the indexes

SHOW INDEX FROM ws_call_logs


it give You idea - which index better to use in this case

without information about data, general ideas:
 - index for created_timestamp - good candidate

You can or create index separate for created_timestamp only, or create index for 3 columns:
core_id, hit_status_code, created_timestamp - columns in index must be in same order as used in query

and last SELECT * not give ideas about data size, even You request 25 records, but before server must sort records by DESC