There are actually two issues here. The first is what appears to be a marketing issue with Garmin (and they're not the only ones doing this!) They always seem to introduce and ship product that only has enough internal memory for the current maps. Soon after updates come out the consumer runs into the memory limitation and the most obvious solution is to upgrade to a newer unit. I've got a drawer full of Garmins because of this.
To be fair though this memory limitation may not be totally Gramin's fault. There is an old law in computing that if the hardware engineer builds a system with "N" resources, the software engineers will eventually write code requiring "N+1" resources.
The second problem is an anomaly in the Garmin procedures for updating maps. As I recall there are two basic ways this can be done. One is to download the entire map to the user's computer, then install from the computer to the Garmin. The second is to download the map directly to the Garmin unit via the user's computer. What I've found is that one method seems to think it needs enough space on the Garmin for the entire new map and it doesn't calculate the space that would be freed up removing the old map. The other method is a bit smarter and it includes this in it's memory calculation.
Two other solutions I've used are to first delete the map file on the Garmin before starting the update. Obviously doing a full backup first! But there are other files associated with this that must also be removed so this is kind of a risky approach. The other solution I've used is to use the Garmin application to build custom maps for download and select the sections from the Garmin maps downloaded to the user computer. I've gotten pretty close to getting everything loaded on my Garmin using this approach.
Another thing to consider is reducing or removing the custom POI files, the voices you don't use, etc. Most of these are pretty small files, but every little bit helps.