I did this once for a similar situation:
In the table that feeds your combo box, add a record where the value for the combo box will be "*". If you have separate value and text for your combo box, you can make the text "All". Set the value of the combo to "*" either in the form_load or whatever.
Then in your query that references your combo, change the criteria's "=" to "Like".
Specific values will match without wildcards on the Like criteria, but if you leave the * in the combo, all records will be pulled.