select count(*) in mysql 5.5 innodb-- rewrite advice?
Since you already have the necessary indexes, consider the next thing: Amazons RDS

You are most likely using the default settings. You cannot effectively tune InnoDB for multithreaded/multicore usage in smaller RDS server models.

As to server model usage of memory, here is a chart

MODEL      max_connections innodb_buffer_pool_size
---------  --------------- -----------------------
t1.micro   34                326107136 (  311M)
m1-small   125              1179648000 ( 1125M,  1.097G)
m1-large   623              5882511360 ( 5610M,  5.479G)
m1-xlarge  1263            11922309120 (11370M, 11.103G)
m2-xlarge  1441            13605273600 (12975M, 12.671G)
m2-2xlarge 2900            27367833600 (26100M, 25.488G)
m2-4xlarge 5816            54892953600 (52350M, 51.123G)


Since count requires passing through many data and index pages, try using a bigger server model.

I have discussed this before:


Aug 02, 2012 : Local database vs Amazon RDS
Feb 26, 2013 : MySQL optimization


Give it a Try !!!