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.
The one exception is when the last name itself counts as a nickname.
There are various ways this works. In the Bothnian region where I grew up, 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. 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.
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.
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" followed by their first name while "Sie" is used at the same time.
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.
Portuguese also has informal and formal pronouns, "tu" and "você", respectively, but their usage is a bit weird. "Tu" implies a "first name basis", as in proximity, although lots of people are known by their last name, even to friends. "Você" implies a last name basis, but the pronoun itself is never used. The verbs are conjugated in the "você" form but either the person is address by title or no pronoun is used. (Sentences in Portuguese can be built without a subject if it is clear who it is.) Talking to someone using the word "você" is considered downright rude. On the other hand, Brazilian Portuguese speakers seem to use "você" all the time and without much trouble.
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.
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.
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.
35+ years after his death, you still only need to say Elvis.