How would a brand-new expat boss get on well with his Vietnamese team?

Ex-pat eh? Then you got things different than an outright foreigner. The minefield is certainly bigger and more dangerous.
1. Stay. Away. From. Politic. Discussion. This minefield is true for both foreigner and ex-pat but it's more dangerous for the latter. You are not to enter such discussion especially when it turn to Vietnam's situation. If you are wrong you are wrong but if you are right you are up people's nose. Even if your Vietnamese employee or fellow workers harping about the corrupt of the system or politicians, you are to nod politely and refrain from comment. Vietnamese complain about them is one thing, foreigners and ex-pat dont have that right.
2. Dont compare Vietnamese business environment with other nations' environment. I know you may not feel alright with the way things stand but comparing them dont change things and will annoy people. A classic response for such comparison is usually on people's mind and/or tongue "If things are so good over there why dont you pack up and go there". As you can see, such response is counterproductive. If you want to change things You can insist people follow your conditions because they are YOUR conditions, ie the boss' way, and they understand that. Boss bossing employees around is nothing new under the sun, after all.
3. Tits for tats. IF you dont want to follow certain custom, like day-off for grandma's funeral (in a manner of speaking) you should compromise in other, obvious, ways to 'make up' to your workers. Nhau, ie 'after-work drinking sessions"? That's personal entertainment. But Gio Chap Ong/Ba, ie "annual rememberance of Grandma's death day" is personal duty. They have a duty to do/join their family's occasions and it's an issue you can compromise. As for the 3000 staff roster, with major of name being Thuy, nothing easier. You just use their name only, no last no middle. Chances are you mess up less than trying to use full name.

The kind of person who chooses to make the "leap" of coming to work in a foreign country so far and different from home is usually a fairly outgoing person with a positive attitude. I have found most Vietnamese people to be generally very smart, dedicated, helpful and hard-workers. In "most circumstances", this creates an environment for the boss and the team to become very close and productive; however, as with most things in life, the Devil is in the details. Think positive!

I think there are a few variables to consider and the expectations of both the organization and employees. In some ways I was lucky enough to start at the bottom, in an apparently well managedcompany. Reflection shows that the issues, there particularly, will continue regardless of effort.
Genuine international companies will have clear objectives and org culture in place which hopefully expect and facilitate very clear communication at all levels and actively encourage contributions that will benefit both company goals and employees value. In thois situation the new expat-boss will be taking over established systems with a view to enhancing and developing over time. This should be team work and during this time when everyone is working together, everyone has the opportunity to get to know each other and have some fun professionally and socially along the way. In this environment it is easy to see how the company has become successful. Happy employees are more productive and this has been shown to improve bottom lines.
Should the new expat boss arrive into a JSC which is for all intent and purpoae a local company then he/she will need a well thought through induction programme which includes not only expected business practices but also the social and cultutral expectations of his new team. Without thisit is very possible that they will unknowingly be upsetting staff members for different reasons everyday. They might fond it very hard work getting the simplest of jobs done and feel that those around are not too happy, but how would they know??
All things considered, regardless of company position and employees if you make sure from the beginning that everyone knows that they are there both for their own needds and to help achieve the companies goals. Make the goals clear and after that communicate openly and expediently on all matters that would divert from achieving the companies goals. Expect mistakes to be made by everyone and provide knowledge and support when needed to solve the problem. Happy working days and very social evenings.

Great question Tue Minh :) and great responses!

Here are my suggestions:
1. Immediately identify and seek friendships with other foreigners who have proven positive relationships with their Vietnamese colleagues. Learn from them and seek their advise. Bimo would be a great relationship to have :D
2. Give him/herself time to find the balance in real success - results AND relationships.
3. Define what are his/her "must have" and what can be flexible with. Choose the battles wisely, don't fight unnecessarily over differences that are not important and can be flexible with.

Is this a real scenario for you right now? :D

.well, one thing he would have to do to get along with his Vietnamese team is to understand Vietnamese's CULTURE and study how vietnam economic systems work

.the problem is: will he? but if he wants to survive, he better be!