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.
If you don't have either, then there is still a way to do this, but it's more of a "some assembly required" approach, and you may need a spare ATMega chip on hand*. You will need a solder-less breadboard for this, though.
*I'm not 100% sure a spare ATMega is needed, and you can use the Ardunio as an ISP without one installed. I doubt it's the case.
**The method will work with the Uno board, and there are instructions for older boards too, if you have one.