Why is "Fräulein" considered offensive, as opposed to "Frau"?
Does Fräulein imply that the woman being addressed is not fully a Frau? Does it imply a lower class status?
Sorry not to answer the question… but this link sheds some light on the surrounding issues! BBC News feature on a French town banning the word for 'Miss'
Just an aside on the the second question, since the main one has been answered well. Definitely no associations of lower class whatsoever. Actually the opposite is true to some extent. While most modern connotations of *Fräulein* are almost identical to those of *Miss* in English, *Fräulein* can also be used in contexts where it denotes nobility: "adliges Fräulein". This dates back to the time when *Frau* was still meant noble lady, *Frauenzimmer* referred to the non-noble women surrounding one, and the normal word for *woman* was *Weib*.
Just as relevant for German *Fräulein* as for English *Miss* (or Hofstadter's *Niss* referring to unemployed blacks): "A Person Paper on Purity in Language" by Douglas Hofstadter. The full text should be easy enough to find with Google.
Fräulein is a diminutive ('Verniedlichungsform') of Frau.
Diminution is considered an intimate act, used a lot with nicknames couples give each other (Häschen, Mäuschen, Bienchen, Bärchen) or for "lovely little beings" like children and pets. So using Fräulein has a touch of intimacy not convenient to many women.
Addressing an unkown woman as Fräulein can be considered as impolite as using Du without having been offered it. The word Fräulein was particularly used to call waitresses and other female assistance in service jobs (not necessarily a bad status, even a female manager of an hotel would be a Fräulein).
Until the beginning of the 19th century the word Frau was only used for royal women, a Fräulein was their female child. Within the 19th century the word meaning changed and became used for women having a profession. This usually ended with marriage (in some cases, e.g. female teachers, you had to be unmarried to work). This indicated that a Fräulein was unmarried and "free to go". This part of the name didn't change even when getting very old as long as you didn't marry (and gave up the profession).
The usage of Fräulein is discouraged by the state since 1972 in Germany. In the same decade the feministic movement pointed out that using the diminutive form changes the gender of the word from female to neutrum, this can be considered equally to not acknowlidging the gender of a person but is felt by many as a philosophical question. Since most of the time diminutives are used to address pets and children, the conclusion that Fräulein are not seen as independent and self-determined beings can't be disproved.
"touch of intimacy"? If this were Wikipedia, I'd slap "original research" on it. Here, I call it speculation.
I made a logical chain, is there something not clear for you or an assumption in the chain you'd like to discuss?
Just as a warning for people reading this: This answer is just wrong. There is nothing intimate about calling someone „Fräulein Müller“. Also, as correct answers have pointed out, this used to be the correct way to address an unmarried woman. It is just not used anymore, for reasons that also have been pointed out.
@CarstenSchultz Please give arguments for your comment, help to improve the answer and don't forget the bigger picture (we're talking about at least Germany, Austria and Switzerland and we are talking about the current point of language development) of the language. I know that using Fräulein was common, but it isn't anymore and I tried to lay out the reasons. Your phrasing implies absolute knowledge ('just wrong', 'nothing intimidating') but without argument it seems to be just biased. Thank you.
While all that may be true, it never really made sense to me. I'd feel equally weird saying to a twenty-something I don't know (neither name nor marital status, nor even if she's a higher up or a visiting daughter) and is standing amongst a group of men that I need to pass in the hallway: "Verzeihen Sie, Frau." (as opposed to the only thing that would make sense to me and NOT sound half as rude: "Verzeihung, Fräulein.") as an English native-speaker probably would in saying "Excuse me, Ma'am" (instead of "Pardon, Miss", for instance). Argueably in that case the English would be less rude.
At this moment you may realize, that talking to women respectfully is quite often a bit awkward (in german ;). The honorific for a woman would be "Dame", but isn't used in day-to-day german except for addressing a group ("Meine sehr geehrten Damen (und Herren)"). The "right" way to do it would be: "Verzeihung, werte Dame, dürft' ich vorbei?" - but that's considered old language. So most just drop any honorifics and go with "Lassen Sie mich bitte durch".