To update firmware, use the web interface built-in to the FRITZ!Box.

The Firmware Recovery Utility should only be used in the event that your FRITZ!Box firmware update fails.

For more info, see: http://www.internode.on.net/updatefritzbox