Summary of the situation
Memory cards are Compact Flash cards (CF, large and thick, mostly on professional cameras) and Secure Digital cards (SD) universally used now, in two physical formats: normal (post stamp size) and micro sd format (for smartphones, usually delivered with a post stamp size adapter).
I will mostly speak of sd cards, the only format I widely use now (2015).
These cards are of three kind, historically and by size.
Up to 4Gb, standard kind. 4Gb standard are not that common.
4Gb to 32Gb SDHD card (notice the "HD" part). A SDHD reader can read smaller cards, but not the other way round. If you can't read a 4Gb card on a device, it's a SDHC and the device is old... should not happen in 2015.
64Gb and up (for now), SDXC cards. Until recently, these cards where very expensive and they need a special reader (downward compatible, of course).
The read problem is mostly about software, so computer readers read all.
The other parameter that matters is speed (it's common to speak about speed, when in reality it's a flow rate or here bit rate). The card have a speed index (from 2 to 10), should say the speed in Mega bits per second, but no card really respect these numbers. A new high speed index have been created with two numbers, 1 and 3, only to make things less obvious...
The speed problem is high because devices are not that clear about what speed they need. Many video cams asks for cat "4" (should be 4Mb/s), but this number is very low if you look at the real specs. fact is probably there is a very fast large buffer in the device, but for continuous shooting like in video, the buffer is soon filled.
I shoot in medium quality (I shoot in night scenes, with odd lights, so the image is not that good anyway), but it is still HD 1080i at 17Mb/s, so even a class 10 card is not enough. Then I never had problem, so...
But if you shoot with 1080p at 60 images/s, you may have as much as 60Mb/s and this needs very expensive cards. Specially, professional devices like the Canon 5DMKIII can use very few compressed formats (no interpolation between images, think at jpeg images one after the other), hence the speed.
Why is it a problem
It's a problem because the SD card makers do not give reliable writing speed, the only one that matters. They sell very expensive cards saying "buy them". But I want to buy cheap cards!
There is an other extremely odd problem. You may buy "fake" cards. Fake as fake size. A 128Gb card is really a 8Gb one! And these cards do say they are 128Gb! But when you write after 8Gb, they only write again the same place...
Fake cards verification
There is one and only one software that can answer the question: is this card a fake or not. It's h2testw.exe (see https://sosfakeflash.wordpress.com/2008/09/02/h2testw-14-gold-standard-in-detecting-usb-counterfeit-drives/).
This software have to be used on an empty card, mounted and accessible by the user (no necessity to be administrator).
Linux users can run it through wine, but this makes it difficult to find the card in the reader, but there is a linux version (http://oss.digirati.com.br/f3/).
These software have to be run on any card (and it takes several hours!!). At the end they give a speed value that is probably the most reliable, then not always the same.
On linux, you may have to download f3 and run it (I have it in my ~/Download/f3-05), that is run ./f3write and may be ./f3read. As it runs on a mounted device, finding which is easy, only go there with Dolphin.
2023 Tumbleweed On 2023 Tumbleweed, f3 is available from YaST (just search for f3).
Most simple speed test is (in linux) hdparm -t that gives some read value.
An other way is using "disk" (in fact gnome-disk-utility).
An other is using rsync with any file, rsync -v gives a summary of the copy operation with speed estimation.
But the real test (boring) is to fill the card with your video, letting the camcorder run as long as necessary.
When you have a video file, it's possible to use mediainfo to get the Maximum Overall Bitrate. An other way is to load the file in almost any reader and write down the clip duration. then you can divide the file size by the clip duration in seconds. Do not forget to x the result by 8 (bits in a byte), not to be frightened by the low speed.
An other problem is that some utility gives bytes (MB/s), others gives bits (Mb/s), other do not say (M/s) and this is only random values, because many bit rates a variable (VBR: Variable Bitrate Recording), depending of the file content.
What I see is that test done on my computer (no so bad one) never give more than around 30Mb/s speed, but various cards of unknown brand do accept up to 80Mb/s on my Canon EOS 5DMKIII. So I guess the culprit on the computer may be the interface. I use the device built into my HP tower, I don't know how it's connected to the mobo bus. I tested SD cards and a cheap 64Gb 800x CF card (at €46.20, a very cheap price atm), both without problem (and a 30 minutes run for the CF card on the 5D).