It is not unbelievable. I don't fully understand the fuse bits, but I do know that you can rewrite them just like you can upload new sketches. However, you need to be very careful setting fuse bits because they configure how the chip operates, and thus how you can connect to reprogram it. For example, setting a fuse bit to use an external oscillator when none exists makes it so that you can't use the chip at all unless you wire up an external oscillator.