However I didn't do any lock bit/fuse changes. Is that necessary?
Yes, you'll require fuse changes to set the boot-loader size and oscillator settings. The boot-loader makefile contains these.
The fuse/lock bits from a brand-new Atmega.
The fuse/lock bits from a Diecimila boot loader. (Amusingly it's destined for a MaxSerial kit.)
Does the crystal has to be 16Mhz exact or 12MHz or 20Mhz would also work?
The crystal must be 16MHz. Otherwise you'll need to recompile the boot loader. If you don't have 16MHz crystals or resonators on hand, you can use the onboard RC clock (@8MHz) and the lilypad boot-loader.