That sounds like data rate mismatch between PC and bootloader.
Do you have the right board type selected?
Sometimes you're better off after big changes like you did to re-boot to a known configuration and go from there.
I aggravated myself for hours once when I re-bootloaded my Duemilanove, only to have unknowingly put the Uno bootloader, and then have every serial upload fail - I had Duemilanove selected for the board , so PC was using 57600, while the board thought it was an Uno and looking for 115,200.
Seems like one or the other could be made a little smarter to determine a matching baud rate.