I am trying to do this without a crystal...
All of the bootloader, UART and sketch code timing is based on a known crystal speed, that's why a 16MHZ crystal is specified. Get a 16MHZ crystal and try again.
Unless you have edited an recompiled a new bootloader, your choices for "F_CPU" are 8 and 16 MHZ.