There are 3 sorts of memory: program memory (PROGMEM), RAM and EEPROM.
By the sound of it you have plenty of program memory left but have run out of RAM (you only have 2 Kb of RAM).
Look up for ways you can put static strings into PROGMEM. If you don't they get copied into RAM.