Why my Arduino Uno R3 doesn't work with a recompiled optiboot with BAUD_RATE=57600
Chris Stratton's comments helped me find a workaround for my problem. It looks like the version of optiboot I was working with (see source-code here) doesn't work properly at 57600 BAUD with Arduino Uno without modifications (that I don't know how to make). So I compiled the bootloader with 76800 BAUD, configured the IDE accordingly, and all my boards started to work fine with it.

It is still unclear to me the reason I one can't use 57600 BAUD, but I'm too pragmatic and too little knowledgeable to go after the true answer. So, I'll take Chris' word for it. He said this: 


  Basically, 57600 does not divide in 16 MHz nicely when the 8x or 16x oversampling of the hardware UART is taken into account. My gut feeling is that different implementation are using different approximations. If they used the same approximation then even if "wrong" things would be basically fine (especially as the hardware design is similar), but if they are are off in opposite directions it could be unreliable. If you post the exact bootloader source you used we can see for sure - some optiboot source I just looked at seems to actually be using a software UART for 57600.


That's the end of it for me.