What could be the reason for potentially unstable bootstrap bca confidence intervals when R=10000? I am using the R package boot to bootstrap Harrel's C Index with different Cox models. My sample consists of about 700 cases with 90 events.
> boot.ci(boots[[2]], type="bca")

BOOTSTRAP CONFIDENCE INTERVAL CALCULATIONS
Based on 10000 bootstrap replicates

CALL : 
boot.ci(boot.out = boots[[2]], type = "bca")

Intervals : 
Level       BCa          
95%   ( 0.7354,  0.7376 )  
Calculations and Intervals on Original Scale
Warning : BCa Intervals used Extreme Quantiles
Some BCa intervals may be unstable

I understand that this warning is common when the number of replications is too low, but  thought that 10000 would suffice. Can I expect to not get this kind of problem when I further raise the number of replications, or is something different wrong that more replications won't fix?
 A: The issue is with the original sample size being small not the number of bootstrap replications.  Increasing bootstrap replications just makes the Monte Carlo approximation of BCa close to the BCa estimate.  The variability of extreme quantiles depends on the original sample size.  What was the original sample size n.
A: The message is generated when intervals use the upper or lower 10 order statistics. The following code reveals the indices of the order statistics used in the calculations:
boot.ci(boots[[2]], type="bca")$bca[2:3]

If the first is less than or equal to 10 or the second is greater than or equal to R - 9, then the message is triggered. In your case, R = 10,000.
You can verify this by looking at the code for print.bootci:
getAnywhere(print.bootci)

Near the bottom you'll see:
if ((bcarg[1L] <= 10) || (bcarg[2L] >= R - 9)) 
        cat("Some BCa intervals may be unstable\n")

bcarg is defined higher up in the function and consists of the indices of the order statistics.
One way to get rid of the message is to decrease the confidence level from the default of 0.95 to, say, 0.90.
boot.ci(boots[[2]], type="bca", conf=0.90)

