Both of our daughters did this, and it wasn't just the car seat, it was strollers too. They hated to be strapped into something. We made sure the straps weren't hurting them in any way. One thing our pediatrician suggested was to make sure that we didn't just feed them before putting them in a stroller or carseat because the sitting position could be uncomfortable with a full belly.
My theory though, was that they just didn't want to be set down, separated from their mom. My wife is a stay-at-home mom, and the girls were used to being around her all the time, and if they needed something, they could cry (0-6 months old) and mom could fix it for them - except in the car seat. I think my girls were upset because they wanted to be held, and knew mom was sitting right by them but wouldn't pick them up.
We became nearly anti-social during these periods of our girls' lives because driving anywhere with them nearly drove us insane.
One day, I finally recorded my second daughter in the car. This was a 45 minute car ride, and I am not even joking - she screamed like this the whole time. We made the mistake of pulling over and trying to comfort them one time - yes, they stopped crying as soon as we had them out, but then we had to put them back in to finish our trip and the screaming was 10 times worse. If we were going to make the trip, it was best to make it as quick as possible. This sounds harsh, but we made sure that everything in the seat (we tried different seats too) was comfortable, they weren't in pain, etc. I really believe they were just mad that we weren't picking them up when they cried - in fact, I even called my 3 month old daughter spoiled on one or two of these trips! :)
They eventually grew out of it. Our first born still did this on occasion until she was about 14 months old (even in a front-facing carseat). Not consistently, but when she got it in her head that she wanted out of the carseat, she would scream for the rest of the trip.
I guess this really isn't an answer but more of a "You're not the only one". I can't help but wonder if babies who are around their moms all the time are more prone to this?
I just had to share the recording too, so others could agonize like I did... Just crank up the volume and put it on repeat for 45 minutes ;)
Edit December 2015
I should add that we had a third child after I wrote this answer and he traveled in the exact same car seat as our first two children - he never screamed or even fussed. That leads me to believe that it wasn't due to an uncomfortable carseat, but more the personalities of the our first two children.