Take a deep breath, count to ten, and smile. Repeat. Below is a reenactment of my first trip to the Taiwanese (The Other China™) “embassy” in Bangkok to pick up my resident visa.
{10:00am - irae waits 30 minutes after taking a number at the information desk. His number is called. Confident that his application has been prefiled by the school and authorized by the Ministry of Education, he makes his way to the window}
irae: Hello. My name is irae. Here is my passport. There is a cable from the Ministry of Education waiting for me. 
visa officer: No, there isn’t.
irae: Are you sure? My school has made the application, and the cable was sent last week.
visa officer: Yes, I’m sure. You’ll need to fill out an application and take another number.
irae: Okay. 
{irae, having had the foresight to bring all of the necessary supporting documentation with him to Thailand, takes a new number and sets about the 40 minute task of rewriting the application. The number before his is called, and then the guards start evicting petitioners from the reception area for lunch. irae wanders out into the blazing Thai afternoon, has a plate of pad thai, reads his book till 2:00, then returns to the reception area. His number is called, and he returns to the window.}
irae: Here’s the application and all of my supporting documents.
visa officer: This seems to be in order. Now we’ll need to cable the Ministry of Education and wait for their reply. It should take about four working days.
irae: But I’m fairly confident that the Ministry of Education has already cabled authorization for my visa.
visa officer: Oh. You need to go check for your cable at the information desk.
{irae smiles, thanks the visa officer, and walks to the information desk.}
irae: Hello. My name is irae. Here is my passport. There is a cable waiting for me from the Ministry of Education.
information desk clerk: No, there isn’t.
irae {smiling}: Yes, there is.
information desk clerk: Okay. Look for your name in this book.
{irae finds his name in the book, and his cable is given to the visa officer at the window. Three minutes later, irae has his visa and is free to depart for a week in Krabi province. It is now 3:00pm.}
I’ve been in similar situations on average once a week for the past decade. Keeping your cool can transform an impossible situation into one that merely wastes an entire day or two.
The cool thing about culture shock is that it works like a sine wave. Sure, there are times when everything sucks and all you want to do is get back to a place that makes sense, but there are an equal number of days when you’re just goofily ecstatic to be where you are. Over time, the rollercoaster ride smooths out into the usual pattern of wake, work, eat, sleep, and then you’ve gone native!
Learn the pinyin romanization system before you leave (it’ll give you a way to visually represent words that you hear so that you can write them down and remember them when you’re learning), and bring a couple of phrase books and dictionaries. My personal favorite is a 1946 US Army phrasebook which lists such useful items as “Put your hands up!” and “Don’t try anything funny!” As a rank Taiwan newbie, I used to walk into restaurants, show them how much money I had, and point to the phrase “What do you recommend?”. This worked well until I stumbled into a seafood restaurant (indistinguishable from the run of the mill noodle shop to my eye) and showed them my NT$70 (three bucks). I was shown to my table, and eventually presented with a plate of celery and a bowl of mayonnaise. A couple of guys from the national opera company noticed my plight, invited me to sit with them, and even saved my face by “sharing” my celery while offering me sashimi and other goodies.
It’s been my experience that Chinese culture is extremely beautiful on a personal level, but falls apart rapidly if you enter any office (government or private) for any reason. The expat engineers over here have a favorite expression, “5000 years of civilization unimpeded by progress”.