Try each of the following steps in order until the issue is resolved:

1.    Ensure the Addressee field is selected on the mailing
2.    In Mail, highlight Labels
3.    Open an existing mailing parameter or click New to create a new set of parameters
4.    On the Fields to Include tab, select ConstituentInformationAddressee as a field to include in the mailing
5.    Use the arrows to move the field to the top of the list of fields
6.    Select the appropriate addressee format
7.    Ensure the label is large enough to print the name and all address lines 
8.    Ensure the correct country is selected on the address
9.    Modify the country's address block to be formatted correctly
10.    On the General tab, ensure the labels are selected to Create for Constituents
11.    Recreate the labels