as mentioned above, you may be able to optimize your code - or - if you have lots of constants, or large string, you might be able to externalize them (eeprom, SD, flash). However, unless there is a large amount of these components this may not really work because you will need to add code to communicate with the devices.
It has been suggested you upgrade to a mega - that will certainly solve your problems - but at a fairly steep price. There are other alternatives that might work for you - such as LeafLabs maple, or ChipKit uno which has 128K of flash.