To the best of my knowledge, the current version 6.1 doesn't support Labels with Polygon mark types. Version 7.0 due out in approximately 90 days will support dual-axis map charts which will permit you to have one mark type be Polygon, while the second overlaid on top could be Text or any other mark type.
I have attached a screenshot of my polygon map of zip codes with an overlaid "Response Rate" measure using Tableau 7.0. If you want to try it, you can request admission to the beta program at email@example.com.
Others may know a workaround with 6.1, and I look forward to hearing their input.
Hi John - can you post your actualy workbook? I'm attempting to do this in 7.0 and am stuck on the dual-axis map chart idea. Have the thematic mapping part down, just can't figure out how to get the labels on.