As I understand it, clock speed is hard-coded into the bootloader, so changing the crystal isn't enough to change the speed. You would need to program a new bootloader in as well.
Given what we've been discussing about clock dividers above, it would seem that changing the crystal isn't actually necessary - a bootloader that sets the clock divider would suffice.