That is strange. Sounds like it's not a 'true' Uno but rather a clone version that used the older bootloader, as I'm pretty sure the 'official' Uno board was released with the higher speed bootloader only. Can you determine what kind of USB serial converter chip it has on the board?
Anyway if you have access to either a hardware ICSP programmer or even another arduino board you can as CrossRoads said pretty easily said just burn the proper bootloader into the chip. Also you could buy a 328p chip that already has a Uno bootloader chip burned into it, several vendors offer that at around $6 + shipping or so.
Lefty