Petit mystère de MySQL

Attention : ceci est un billet plutôt technique (vous êtes prévenus dès le début).

Comme Kappea comporte une partie géolocalisation, j'ai une table cities qui comprend pour l'instant toutes les villes de France (DOM-TOM compris) avec leurs coordonnées (latitude, longitude). Il n'y pour l'instant que les villes française, mais comme je prévois d'ouvrir Kappea à d'autres pays (tiens, une révélation !), j'ai bien sûr un champ country qui est un CHAR(2) et qui est indexé.
Bien. Le décor est planté. Voyons voir ce qu'il y a de mystérieux...

mysql> SELECT COUNT(*) FROM cities;
+----------+
| COUNT(*) |
+----------+
|    38949 |
+----------+
1 row in set (0.02 sec)

mysql> SELECT COUNT(*) FROM cities WHERE country = "FR";
+----------+
| COUNT(*) |
+----------+
|    38949 |
+----------+
1 row in set (0.06 sec)

Jusque là rien de bien spécial, puisque j'ai bien dit qu'il n'y a que des villes françaises.
Mais si on analyse la requête, ça devient surprenant...

mysql> explain SELECT COUNT(*) FROM cities;
+----+-------------+--------+-------+---------------+---------+---------+------+-------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows  | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | cities | index | NULL          | country | 2       | NULL | 38958 | Using index |
+----+-------------+--------+-------+---------------+---------+---------+------+-------+-------------+
1 row in set (0.00 sec)

OK, il passe toutes les lignes en revue. Logique, puisque je ne restreint rien.

mysql> explain SELECT COUNT(*) FROM cities WHERE country = "FR";
+----+-------------+--------+------+---------------+---------+---------+-------+-------+--------------------------+
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows  | Extra                    |
+----+-------------+--------+------+---------------+---------+---------+-------+-------+--------------------------+
|  1 | SIMPLE      | cities | ref  | country       | country | 2       | const | 19479 | Using where; Using index |
+----+-------------+--------+------+---------------+---------+---------+-------+-------+--------------------------+
1 row in set (0.00 sec)

Et là, je ne comprends plus. Alors que toutes les lignes ont le champ country à la valeur "FR", la recherche par index n'en indique que 19479. Mais la requête donne le même résultat...
Je crois qu'il reste encore pas mal de secrets que je n'ai pas percé dans les arcanes de MySQL.

PS: j'ai une version 5.0.32 avec la dernière Ubuntu.

Si jamais un pro de MySQL passe par là, je veux bien quelques éclairages.