You all were right in that the issue involved the bootloader, and that my guess for what the problem was is incorrect. It turns out that in the Arduino IDE I needed to choose Tools -> Processor -> "ATmega328P (Old Bootloader)" instead of "ATmega328P", and then I was able upload a new sketch successfully.
Thanks for the help!