Update: Various updates to Civicrm means that 4.6.2 can now be changed to handle Mailing labels with Chinese characters without the biggie - everything is lost when you update civicrm. The following code has been updated to reflect this and so only works on 4.6+ versions. The solution comes from various web locations with various problems that needed to be fixed.

I had to get Chinese (Simplified UTF-8) working with mailing labels in Civicrm (4.6.2) - Chinese worked everywhere else except in mailing labels - were we had ???. In Civicrm's mailing label routine - a pdf file is created and the problem has to do with not having the right font. The mailing label in Civicrm uses tcpdf to make the mailing labels. This is one of 2 pdf programs - the other one is dompdf - which is used in mail merge for letters and has no problems with Chinese.

The solution involves:

1. Make sure that tcpdf fonts are not overwritten on upgrade of civicrm
   1. We need to copy the fonts folder of the existing civicrm's tcpdf to a new location - e.g. /home/tcpdfonts
      e.g. cp -r <civicrm program root>/packages/tcpdf/fonts /home/tcpdfonts
   2. Tell civicrm's tcpdf to use this new location instead of the default. We do this by adding the following line to civicrm.settings.php file: 
      define('K_PATH_FONTS', '/home/tcpdfonts');
2. Add Chinese Font to tcpdf
   1. Adding a font that has UTF Chinese fonts in it - One free option is Droid Sans Fallback - as suggested by this blog 
   2. Copy the downloaded ttf font to  tcpdf font directory that you had moved in step 1 (/home/tcpdfonts)
   3. Rename the font so that there are no capitals or spaces - e.g. to droidsansfallback.ttf
   4. In the <civicrm program root>/packages/tcpdf/tools directory - there is a tcpdf_addfont.php script - run it from the command line in the font directory (e.g. /home/tcpdfonts) - so 
      <civicrm program path>/packages/tcpdf/tools/tcpdf_addfonts.php -t TrueTypeUnicode -i droidsansfallback.ttf --outpath /home/tcpdfonts
      Note: use -t TrueTypeUnicode - I used TrueType initially and it did not work.
      Note: You need to add an outpath otherwise the output will be put int he default font location - which is <civicrm program path>/packages/tcpdf/tools/fonts. If this happens move all the droidsansfallback.* files to /home/tcpdfonts
3. Tell Civicrm about the new font - you no longer need to change Label.php - which will be overwritten on each update - Instead you add the addition font information to civicrm.settings.php
   global $civicrm_setting;
   $civicrm_setting['CiviCRM Preferences']['additional_fonts'] = array(
       'droidsansfallback' => 'Droid Sans (UTF-8)',
   );