Count(1) vs. Count(*) is a urban myth, and I don't really think the complex index will be a significant overhead.

The plan looks OK to me. So, how many rows are selected by:
SELECT COUNT(*) FROM CART_STATS WHERE COMPANY_ID = 8170926;

It could be that you are having to read a vast number of rows in order to do the rest of the logic . . . ?