The best way to do this is to flip the problem around on its head.
1) Instead of making the date field a formula field, make it a plain date field.
2) Then remove the choice of "Complete" from your multiple choice "Status" field.
3) Create a formula text field called "Computed Status".
4) Put the following formula into the formula property of the "Computed Status" field.