Using the entire service, instead of individual layers, worked for most labels.
Although, I have a join on one of my feature classes to a table in SDE, which prevents the labels from showing in the flexviewer.
This is from ESRI:
This is Utkarsh from ESRI Support Services, writing in reference to incident # 1183308 It was pleasure talking to you over phone as discussed you were currently hitting the Following [NIM087311 Map labels do not work in a map service if the feature class resides in an ArcSDE database and is joined to a table.]. The status of the NIM is resolved in the version 10.2. With this information I am marking this incident as closed
Jeff Godfrey