If you are using VMWare ESXi 5.0.0 U1 (the free version), there has been a bug with the virtual machine auto-start feature for quite some time, where machines would not start automatically if they were configured to do so. Up until now, the only fix was to revert back to the old version (5.0.0).
It appears that a patch has been released - see this VMWare blog post for more information. Here's the direct link to the patch on the VMWare website: ESXi500-201207001.zip
Here is a method of installing the patch via the CLI.
I applied the patch against an ESXi 5.0.0 U1 server in my lab by uploading it using vSphere Client to the main datastore, SSH'ing into the machine, and then running the following command:
esxcli software vib install --depot=/vmfs/volumes/datastore1/ESXi500-201207001.zip
I'm hoping they will roll this patch into the next major release... no idea when that comes out though.