Make sure all MS critical updates have been run and rebooted
Make sure User Access Control is off and rebooted
Make sure the A2EService account is part of local administrators
Make sure you are logged in as the service account when you install
If you are running on Exchange 2007 or 2010, make sure you run the Preinstaller included using these instructions:
http://support.diditbetter.com/kb/A2E_214.aspx
Does any of this work for you? Where are you exactly during the install when it fails?