Hi Kris,
Try removing the 'select a state' option, and replace it with an option with a blank value, i.e:
<select name="state">
<option selected="selected"></option>
<option>Alabama</option>
<option>Alaska</option>
<option>Arizona</option>
<option>Arkansas</option>
<option>California</option>
etc.
If the validation is just 'Required', then an option containing a value would need to be selected to pass validation.