America. To clarify, there are the basic Ms. Mr. and Mrs. which are followed by the last name. These are generally used for strangers and when children are addressing a person they're unrelated to. Otherwise, First Name Basis is expected. If a last name is used, it can be interpreted as cold or rude. It's a little more complicated than this due to regional standards, but otherwise, it's fairly standard.
In Scandinavia being on first name basis is the standard.
Likewise, at least in Finland, calling someone by their last name to their face often comes off as downright rude. You may refer to politicians, superiors or teachers by their last name when you're talking about them, but when you talk to them, you use either their title or their first name. If, for example, a teacher is known among the student population by their last name, chances are they're not very well-liked.
Interestingly, in the schools, students pretty much always talk to and about their teachers using their last name (unless the teacher has a nickname, which isn't all that rare either). The teachers, however, call the students and each other by first name. This has even lead to a (usually new) teacher not knowing who a student means if s/he asks for someone and uses their last name.
Likewise in the Finnish Armed Forces, the usual referral is by last name and second person majestic plural. For many conscripts, this usage feels very formal at best and downright hostile at worst.
It's the same in Poland. It's also typical to refer to people that you work with but are not friends with as Mr/Ms/Mrs [First Name].
If two Dutch meet each other for the first time, they will call each other by last name (unless they are under 25 or so, then they will be on a first name basis right away.) but they will switch to first name basis really quick in most cases. Because the Dutch do much business with the Germans, (see below) this tends to lead to awkward situations.
Similarly, in the Philippines, people often refer to each other by their first names, even when only meeting acquaintance, and use their last names only on certain, usually formal, occasions. Exceptions arise when there are people around with the same first name (which happens very often) and so are referred to by their nicknames or last names.
Danish students call their teachers by first name all the way through the education system, sometimes not even knowing their teachers' lastnames. This started after the student protests in 1968.
The one exception is when the last name itself counts as a nickname.
There are various ways this works. In the Bothnian region it's normal for people to refer to even their lifelong friends by only their surname (= the name of the household), since the first name is seen to be of lesser value and generally of no interest or importance. Only between siblings are first names used, and even then only to avoid confusion.
In Iceland the last name is not a family name but a patronym (or a matronym) so it's not strictly a part of your name, it just tells people who your parent is. (Example: Björk Guðmundsdóttir.) So referring to Icelanders by last name only is flat out incorrect no matter how formal you want to be. You'd call the prime minister by their first name rather than last. The correct way of being formal would be to use a title or a full name preceded by Mr/Madam but Icelanders in general aren't very formal. Even first name bases can be too formal, as in some cases (especially with long first names) the informality of first name basis in other languages is instead replaced with shorter nicknames.
Not only does the language French have different pronouns (Tu-Toi for close people, Vous for more formal relationships), the use of names is the subject of a peculiar etiquette: Calling someone by his first name is normally reserved to friends and family, but calling someone by his family name without the proper honorific (Monsieur, Madame) is considered rude, except when there is a certain level of intimacy (for two colleagues for instance). It becomes even more confusing when you go into the written language: when writing about someone in French, you are supposed to use the full name basis without honorifics: for instance, a French journalist writing an article about the US president is supposed to use the Term "Barack Obama": "Obama" alone is tolerated but usually not considered respectful enough, and "Monsieur Obama" is actually considered insulting: confusing, isn't it?
Note that this is also prone to regional variations. In Québec, for instance, using the formal pronoun "vous" with someone's first name is acceptable in certain polite but informal introductions.
German shares the du/Sie pronouns with the French tu/vous in addition to the use of first and second name. First name basis always assumes a close personal relationship or a highly informal social situation, so it's never used for strangers or authority figures, for which such a relationship is considered improper, even if you know each other for years and go along very well. The exception is for children and young teenagers which are always called by first name, but are expected to use the second name form the same way adults do.
Changing from "Sie" to "du" is still considered a big deal by many Germans, who feel a bit of a ritual is necessary. This takes the form of Brüderschaft trinken (drinking brotherhood), which entails the two persons drinking with the arms holding the respective glasses linked. If then one of the two people accidentally adresses the other with <honorific> + <last name>, the other may require him to buy him a drink as a penalty. And addressing someone with "du" and first name still can lead to them testily replying: "Und wann haben wir zusammen Schweine gehütet?" ("And when did we herd pigs together?")
An interesting exception are German universities, where all students are always on first name basis, regardless of age, social background, academical seniority or personal relationship. This is a result of the 1968 students' revolt which affected the way students adressed each other since the 1970s.
Also, in schools teachers start referring to the students with "Sie" and switch on last name basis at the beginning of the 11th grade (most pupils are 16 by this time, thus the change marks the beginning of adulthood). Often though there's no change because the students themselves object the changed patterns.
Additionally, Du usually implies First Name Basis, while Sie implies Last Name Basis. Addressing someone with du and his last name (or vice versa) is ... odd.
Unless there exists a tradition to do otherwise. This is for example the case with nurses who are addressed by their title "Schwester" (Sister) followed by their first name while "Sie" is used at the same time. This is because nurses were almost universally nuns during the time when the German health system was established — and "Sister <Some-First-Name>" is exactly how nuns are addressed.
Historically, German had a quite complex system of addressing people depending on the social rank of the speaker and the addressee. Before "Sie" (third person plural) gradually became the respectful catch-all it is today starting in the late 18th century it was something like this:
"Du" (second person singular) and first name: Grown-ups to children, masters to (junior) servants, close friends and siblings amongst themselves, husbands to wives (but not always vice versa, sometimes women would address their husbands by their last name, vide Effi Briest), and everybody to God.
"Du" and last name (without honorific): Teachers to pupils of a minor age, landlords to peasants etc., masters to senior servants.
"Er" or "sie" ("he" or "she", third person singular) and honorific plus last name: Socially superior to inferior, e. g. a passenger to a coachman, but also e. g. a king to an officer.
"Ihr" (second person plural): Socially inferior to superior, but also monarch to subject in official letters.
In some cases personal pronouns were pretty much entirely avoided and replaced by a more complex honorific such as "Your Majesty", "Your Excellency" etc.; this went with verbs in third person plural.
Simon's Rock College of Bard in Western Massachusetts has this written into the campus bylaws. Everyone is on a first name basis. The President and provost are Leon & Mary.
And then there's Italian, a magical language that has THREE ways to refer to people: Tu, Voi e Lei. "Tu" is like Du or Tu in French, basically something with which you refer to someone you consider on your same level, so to speak. "Voi" is far more high, basically the way you may talk with a Queen or an equivalent. "Dare del lei" is something in the middle: you are showing respect, but let's say that you don't have to bow down when they walk in front of you. Usually the latter is the way you speak with superiors or professors and, if you are a professor at the university, at your students. On the other hand, outside school and work people call each other using their first name, even if they just met. There's no real problem in using honorifics instead of surnames or first names: while the last choice is less polite than the others, it certainly isn't that much of a deal.
It is (or used to be) partly regional, with people in the South using "Voi" where Northerners use "Lei". Under Fascism, "Lei" was officially replaced by "Voi", but that change did not stick.
Portuguese also has informal ("tu") and formal ("você") pronouns, but their usage varies a lot depending on dialect and personal preferences:
In Portugal "tu" implies a "first name basis", except when the person is known by their last name even to their friends, and "você" implies a last name basis, but the pronoun itself is almost never used (the verbal conjugation changes to suit "você", but the person is addressed by a title or no pronoun at all). Talking to someone using the word "você" is considered downright rude.
Rio Grande do Sul, Santa Catarina and some parts of Paraná have somewhat the same tu/você split as Portugal, but the pronoun "você" itself isn't considered rude, and some people conjugate the verb following either pronoun the same.
In most Brazil, "tu" fell into disuse, and most people will use only "você" even on informal and "first name basis" circumstances. Titles as "o senhor" [Mister] are used instead to convey formality and, confusingly enough, with parents in more traditional families.
Occurs in Malaysian and Singaporean society:
Muslim names in the form of A bin B (for males) or A binti B (for females) mean A, the son/daughter of B (the father). It is very rude to refer such people as B, and they are always referred as A.
It similarly works to refer to them as using "son of" (s/o)/"anak lelaki" (a/l) or "daughter of" (d/o)/"anak perempuan" (a/p), i.e. "A s/o B" or "A a/p B". This naming convention is also commonly used among Indian communities which adopt a similar naming system.
The Chinese have their names as last name basis, but some of them were referred by their first name (which is a surname) by people other than Chinese for simplicity. Some of them found out this as odd, though.
In Israel, first name basis is used almost all the time. Students call their teachers by their first names - and if they don't know the name it's "Teacher". While some professors/doctors insist on their title, lots of others don't bother with formality and go by their first name. Heck, even in the army you call officers by their first name. The only time this tropes said "Sir" was in boot camp.
The same instructor-student informality applies to universities in the United States as well. Occasionally you'll run into the occasional professor who sign their messages with their first name, and on rare occasions they even encourage you to address them by first name.
This trope can come up in the military. Since last names are worn on everyone's uniforms, this is almost always what people will use upon meeting one another. Switching to first names usually means that a relationship has become more personal.
In Victorian Britain, calling someone by their first name was unheard of unless you were in a very close relationship (for example, engaged couples or siblings/cousins). Also, social etiquette, especially that involving first name usage, was very strict.
Lampshaded by the Queen herself at the death of Prince Albert, to the effect that no one would be allowed to call her simply "Victoria" anymore...
All Slavic languages use the aforementioned T-V distinction. Russians are very strict about whether they'll call someone by their last name, given name or patronymic. South Slavs however tend to go very quickly from calling someone vi (formal) to ti (informal) and not to do so implies a degree of coldness or even hostility unless there is a significant difference in age, status or the occasion is purely professional.
In Bosnian universities professors, assistants and students call each other "colleague" to emphasise the filial relationship between all members (no matter how junior or senior) in an academic field. Freshmen tend to get a kick or two out of calling the grumpy tweed clad professor that failed them on an exam "kolega" (which besides colleague also means "pal.)"
Few people know that Buryat musician Namgar's full name is Namgar Ayushievna Lhasaranova. She will forgive you if "Namgar" is the only part of her name you can remember.
This is a significant cultural difference between Canadians and Americans. Canadians are often annoyed by the American tendency to quickly jump to first name basis, even while still strangers.
In the United Kingdom, Boris Johnson is one of the very few people known and called only by their first name.
Just about everybody in the west calls Saddam Hussein by his first name, for some odd reason.
After he became ruler of the Commonwealth and well into the Restoration, many Britons would refer to Oliver Cromwell as "Oliver".
Indo-Canadian musician Raghav Mathur is invariably billed by his first name.
Wynonna Judd is usually billed only by her first name.
Similarly, if you say just "Reba", most people will understand that you're talking about Reba McEntire. In fact, all of her albums since 1988's Reba have referred to her only by her first name.
Japanese-American actor Mako Iwamatsu was most often credited as "Mako".
In the NBA from the 80's on, if you say "Magic", "Michael" or "Larry", people know who you mean.
Shaquille O'Neal, Kobe Bryant, and LeBron James are all far better known by their first name (or in the former's case, his nickname derived from his first name) than by their last name. Unlike Magic, Michael, or Larry; the names Shaq, Kobe, and LeBron are pretty much synonymous with the NBA stars even outside the context of basketball. In fact, let's just say that if you're a basketball player who's referred to commonly by your first name, you are a really BIG deal.
Same holds true for "Ichiro" in baseball, whether you're in North America or Japan.
35+ years after his death, you still only need to say Elvis.
Ernst Röhm, the leader of the SA, was the only top-Nazi close enough to Adolf Hitler that he openly and freely addressed him by his first name rather than his title of Führer.