I'm using an SSD1289 here: http://arduino.cc/forum/index.php/topic,140111.0.html
Using a parallel connection on a mega I can clear the screen over 51 times a second. I'm in the middle of finishing up a beta release of a library for it, which I will release very soon.
But regardless of my library, the screen is cheap, it has a touch sensing screen, and works very well with an Arduino Mega ( don't bother with the UNO setup if you want speed ).