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.