I wouldn't be too worried about non-implemented bits reading back with 1 set. That does happen. According to the fuse calculator:
http://www.engbedded.com/fusecalc
both settings of the extended byte mean the same thing (the boot size).
Any other pointers what else to try?
I am wondering about the clock rate. Is this board running at 16 MHz? Also have you got the correct board selected in the Board menu? (Yes, I know it is a beginner question, but that is what I would be checking).
Also can you turn on verbose uploading information, and copy and paste the output you get when trying to upload a new sketch? Thanks.