That's unusual. What programmer are you using, and are you burning the bootloader from the IDE or outside the IDE (not that either shouldn't work, but...)
If burning the bootloader from the IDE, lock bits should be handled, see the board.txt entry earlier in the thread.