Did you test about asking the people to enter the date as ISO yyyy-mm-dd ? I'm not raised in the US and am usually confused of the meaning of some dates, however stating the year first makes it always understandable.
Most people ignored any note about what format the date needed to be entered in. We also found that many people were confused by the ISO format, or were simply irritated by it. The solution presented above has eliminated the most errors and seen the least number of complaints for us.