Arduino duemilanove writing to different memory(flash/EEPROM/SRAM)

Hey i am using arduino duemilanove (atmega 328P). I am using 16 bit ADC interfaced with SPI protocol and then sending data serially into my laptop(reading com port using matlab). problem is I am getting too few samples. I am expecting 500 samples per sec. So Now I want to store data into arduino memory(flash or EEPROM or RAM). EEPROM I checked it takes 3.3 ms to write 8 bits of data which will lead to loss of data as I am expecting 16 bits every 2ms. Is Flash too that slow? I can write to flash using progspce library.
Also note i will be gettting total of 1000 samples per second( 500 for 1 channel 500 for other)
thanks in advance

A sketch can't write to progspace.
Uno only has 2048 bytes of SRAM, and 1024 bytes EEPROM.
Sounds like you need something with bigger SRAM for more temporary storage.
Atmega1284P has 16KSRAM, twice that of a Mega.
I offer an Uno-like 1284P card, kit or assembled:
http://www.crossroadsfencing.com/BobuinoRev17/
Scroll down a little on the web page for:
Core Files for Bobuino '1284P Boards and
replacement Pins_arduino.h to put in Bobuino variant folder

I am ... sending data serially into my laptop. Problem is I am getting too few samples. I am expecting 500 samples per sec.

I would focus on why you're losing samples on your serial connection.
500 samples/s * 10 bytes/sample * 10bits/byte is 50000bits/s, so this "ought" to work ok on a 115200bps serial link. (allowing 10 bytes per sample is pretty generous, too.)