I changed the code to the following:
DCount("*", "tbl_Holidays", "HolidayDate = #" & Format(12/12/2016, "mm/dd/yyyy") & "#")
DCount("*", "tbl_Holidays", "HolidayDate = " & Format(12/12/2016, "\#mm/dd/yyyy\#"))
It made no difference. Still doesn't work.