I spend hours and fouled around with every parameter I could find: cabling, crystal, capacitors, voltage, software - nothing helped.
The UART1 bootloader solved the problem at the very first attempt...
Great - thanks!
Make it available to the general public!
Another "fix" is to use a resonator instead of the more precise crystal. Apparently, there is a Atmel problem with UART0 on just the 1284P-PU packages, not the -AU. With the resonator and lfuse = 0xF7, all the other bootloaders should work.