The 'brains' of the Arduino is a microcontroller called an ATmega. It is a product line from ATMEL (a Norweigen chip company). Just like Intel & AMD release new & better chips each year, so does Atmel. The first versions of the Arduino (up to the NG) used an ATmega8 - a chip with 8K of flash memory and 1K of RAM. Then Atmel released the ATmega168, a drop-in replacement with 16K of flash and 1K of RAM - a really big improvement! Now there is the ATmega328 with 32K of flash and 2K of RAM.
Updating and replacing your Arduino is easy and painless and costs only a few dollars. Your sketches will work just as before but with a little more breathing room.
In order to perform this upgrade you will have to either purchase a preprogrammed chip or program it yourself with a AVR programmer or by 'bitbanging' it.
If you purchased a chip from Adafruit that shipped before Feb 5, 2009 the chip will have the baudrate set at 19200 (same as the older Arduinos). After Feb 5 the upgrade chips were changed to 57600 baud rate (3 times faster!) in order to be compatible with new Arduinos. If you have a 19200 baud rate chip you will have difficulty uploading. Simply quit the Arduino application and edit the file in the hardware folder named boards.txt and change the line from: