Don't do an OTA update, you need to do a full flash using the flashall.sh script or use the windows tool. These erase and repartition everything and are not dependent on size of the update partition.
I recommend you to check the getting started guide available here: IoT - Intel® Edison Board Get Started Guide | Intel® Developer Zone. The SparkFun's guide is not updated.
As jhane mentioned, the methods to flash the Edison module with the latest image are the flashall script and the Flash Tool Lite. The recommended method is using the Flash Tool Lite. You can find this tool in the Downloads site: IoT - Intel® Edison Board Download | Intel® Developer Zone, as well as a setup guide.
The flashall method is an alternative method that uses a script called flashall.sh to flash the module. This method is described in the following guide: How to Run the Flashall Script