I had something like this happen on my very first voice call (Tele2 network, Sweden, no 4G, 3G on, WiFi on, phone resting on a table and using a headset). With my iPhone 4, call quality was always great (but iOS 6 did change something, as I could hear more of my own voice when using a headset than with previous iOS releases). With my new iPhone 5, the other person sounded overly compressed (low bitrate) and the phone cut out too much background noise in a way reminiscent of some Android phones. It also didn't let me hear much of my own voice which is something I don't like - a phone is supposed to let a certain percentage of what goes into the microphone through to your own speaker. However, I had no problem understanding the person at the other end (the quality was just really poor) and she could her me clearly.
I think this is a software issue as it must have something to do with the audio codec. Of course one call isn't much to go on but the fact that the call quality of my iPhone 4 had a major change between iOS 5 and 6 shows that a lot of things can be changed in software these days. I could just have had a bad connection and maybe I should have redialed but time will tell what this is all about. It does seem unrelated to the network.
And to whoever commented about 1990s analog lines: The late 1990s was probably a high point for the phone network, at least in developed countries. All of the important stuff had gone digital and the overall sound quality was just really, really good. No one had invented VoIP yet so everything was 56 (USA)/64 (Europe) kbit PCM, which made for excellent sound quality.