Sadly going to have to agree it's looking likely it's no longer a feature of the system. There's other things that could be tested like artwork being stored as progressive/baseline JPEG's or even as PNG but like every other suggestion put forward here, if it's not given issues before, it's unlikely to be the cause now. That's assuming your other cars are Cadillacs, if they're different brands the issue's completely in the air whether Cadillac even supported it in the first place.
Your best bet might be to take the car back to a Cadillac dealer and see if there's anyone knowledgeable enough to confirm the issue or potentially even restore the functionality (don't know if that's allowed/possible).
It might even be worthwhile trying out playing music through your phone; I was a hardcore believer in an iPod playing through an Aux cable. Worked for me, though not the easiest in a car. 
Tried a USB for a while but felt my car's player was lacking and got fed up maintaining a library of music separate from everything else. I caved and am now sticking with music on my phone where I can update and take my library anywhere and play through just about anything.