It must be that the cell isnt truly blank... have you inserted a space, or perhaps does it contain a formula with an ,"") section.

If your dates are dead-figures and entered manually, make sure they are all definately blank.

If the date is generated by a formula that also returns "" if criteria is not met, you will need to change your conditional formatting to :
Formula Is > =AND(C4<>"",C4>TODAY())

or

Formula Is > =AND(C4<>"",C4>A1)