It sounds like you have an older UNO that had the older version of the bootloader. The older bootloader was larger than the current version and did not leave as much space for program code.
You can update to the current UNO bootloader firmware that is included in the Arduino 1.0 package.
Post back if you need more detailed information about burning a new bootloader or the location of the bootloader firmware files.