When addressing John Doe, would you say "John-さん", or "Doe-さん"?
Does it depend on how polite or formal you're being? Does it also depend on whether the person is a nihonjin, a kankokujin (who have their family name first, not last), or a westerner?
In general, Japanese people will address people by their last name if they are anything but good friends.
So that would be the tendency would be Doeさん.
However when it comes to western people 2 things come into play.
1) Your name might be difficult to say.
2) They might know our custom is to use first names more often.
When I was in Japan and dealing with people I would see fairly often, they would generally ask me what I wanted to be called. I always said my first name because that is how I see myself and because my last name is impossible for Japanese people say correctly.
As for my experience I'd say first name + san is less formal and last name + san is more formal and usually used for ソト people.
As others have pointed out, it's usually a context based system.
If it's a formal situation, and you want/need to show some respect (maybe you're having dinner with your boss), then it would normally be (family name)+title (probably さま or their division title).
In an informal situation or with friends, I've found that it's acceptable to use (given name)+title (probably さん, くん, or せんぱい). Sometimes, you might even be able to drop the title part. Always ask first though as some people, even in informal situations prefer their family name and a title.
I've found in schools (I don't know about college/university, however), that teachers will often refer to their students in (given name)+title format. In this case, the title would usually be くん (but not always). I've no idea whether this is to foster a slightly laid back situation, or whether this is down to the possibility of there being multiple students with the same family name in the same class, though.
Side story: I found, while studying Japanese at university, that some Japanese teachers in the UK prefer the (given name)+さん approach to be very useful. Probably for the same reason as the teachers in Japanese schools.