Bootloader Problem?

It's odd, that's for sure. You could use the "detect chip signatures" sketch to check if the sketch actually uploaded completely.