One of the reasons listed for failures is:
Unsupported software modifications are present.
The Kindle doesn't support software modification, and will be unable to update the Kindle software if it has been modified. Contact the original developer of the software modification for instructions on how to remove the modification.
It seems that amazon has acknowledged the work that is going on here....