Why is this MySQL SELECT performing so slowly despite indexing?
EDIT: Since the first try with a subselect lead into doom, it might be necessary to split the table into a hot range and a "cold" range. That solution only could help if you have some criteria for id_c and id_b, which shows if this id_c will be read often or rarely, for example the age of this. But even deleting from such a big table is not so easy, it would need an optimize which takes ages. It would need some clever ideas to get as little as possible reads which "overlap" between both tables, but since you want to read all rows with id_b from different id_c, there will be cases where you need two queries and adding afterwards.

As already stated in the comments, look into key_reads and key_reads_request with SHOW VARIABLES LIKE 'KEY%';. Check if key_buffer_size is big enough (https://dev.mysql.com/doc/refman/5.0/en/myisam-key-cache.html). You could arrange two different key buffers, one only for that specific table (https://dev.mysql.com/doc/refman/5.0/en/multiple-key-caches.html), one for the rest.

The suggestion with an index id_b, id_c should help a lot, since your query can then be processed completely in index, not from the (not bigger) "real table".

Try doing an analyze table A in low-traffic-times.

It really would help to split the table into many sections, especially for OPTIMIZE TABLE and ANALYZE TABLE, but your kind of query makes that really hard.

Doomed original solution:
I think you create many N x N - block of rows, where N is the number of rows in tableA with identical id_b values, since the join has to combine the id_b - blocks. So when you have many rows for some id_b, time squares up with that number.

It might help to use subselect in that case.

EDIT: EDIT undone.

SELECT COUNT(*), OtherA.id_c 
FROM A OtherA where OtherA.id_b in (
    select DISTINCT id_b from A where A.id_c = [MY_SPECIFIC_C_ID]
)
GROUP BY OtherA.id_c


So the id_b can be selected in one scan and then can be sent through the index to find the right rows.

EDIT: 
The Explain inserted by the Questioner shows that this subselect is a very bad idea in that case, no wonder it takes forever:

EXPLAIN on the suggested query looks like this:

row1
id--------------1
select_type-----PRIMARY
table-----------OtherA
type------------index
possible_keys---NULL
key-------------Uniqueness
key_len---------10
ref-------------NULL
rows------------496167246
Extra-----------Using where; Using index
row2
id--------------2
select_type-----DEPENDENT SUBQUERY
table-----------A
type------------reg
possible_keys---Uniqueness, id_b
key-------------Uniqueness
key_len---------10
ref-------------const,func
rows------------1
Extra-----------Using where; Using index; Using temporary