I have a 16GB, Class 2 card and saving a picture is almost instant. It is possible you got a bad card, or maybe just need to re-format it.
Another stupid thing to check is your review time. Open the camera and go to settings and turn off review, or change the review time. I turned mine off.
If a re-format doesn't fix it, I would look into drive performance applications to test the read/write speed of the card and compare it to others.
As far as buying a new card, I wouldn't bother buying anything over class 4, most phones just can't read/write at those speeds anyway, those are really for DSLR cameras.