I wish I had experienced this sort of thing, but not only have I had all the issues you described from old, poorly kept C41 film, I have also had my negs fade because they are dye based and not silver like true B&W films. True, the negs that I experienced fading with were poorly kept, but any dye based film has it's days numbered no matter how it's stored. It's just the nature of the beast.
Were you looking at the prints or negs? Labs use machines that will auto correct machine made prints from what is on the neg. I had to tell processors to switch that function off when they processed my C41 films because I was unable to see what was really going on w/ my cameras, exposure, etc when they did auto correction. Not all labs would do that for me, but most would.