Es que al no tener la $ que indica el final de la cadena, se captura baja-california seguido de cualquier cosa. Por ejemplo, usando esto obtendrías el resultado deseado:
Código Apache:
Ver originalRewriteRule ^baja-california$ /estados.php?id_Estado=2&nombre=Baja+California
RewriteRule ^baja-california-sur$ /estados.php?id_Estado=3&nombre=Baja+California+Sur