When attempting to replace Polished Andorite with Stone in an area smaller than 4096 blocks, it works fine, but when the enclosed area goes over that number, the command doesn't execute, even though the actual amount of blocks being changed is within the limits.(less than 1000)
Here is the command:
/fill 31 29 13 10 47 -10 stone 0 replace stone 6
Test pics with redstone lamps and lapis blocks:
Edit: If this is intended, so be it, there is a workaround, I just wouldn't think it would be.
The limit exists to prevent ridiculous computations being run. When you filter the blocks, you are still checking all the blocks to see if they match the filter. Is also impossible to calculate exactly how many blocks match the filter without running it on all of them.