We have used about 6 different brands of SD card since we first laid our hands on the Sheevaplug. The slowest were some class 6 Integral Ultimas; the strange thing was that several previous batches of exactly the same model had performed just fine.
The best test that you can do is to compare your results using a completely different SD card, and to perform some controlled tests.
On the slow cards, we had only slightly delayed boot-up. But decompressing a .tar.gz file (an ubuntu rootfs) from USB stick to SD card took 40 minutes when we normally expect it to take 5 minutes.
You'll probably need to quantify the slowness you are experiencing.