Here is how I had to code it:
import time
from datetime import Date
#Sets a variable to hold today's date
currentdate = today()
Process: Feature Class to Feature Class (6)
arcpy.FeatureClassToFeatureClass_conversion(in, out loc, "output_"+str(currentdate)
The result is: output_2014-10-23
The “-“ causes failure as an invalid character