As others have said, I'd suspect an old fuse that was a bit weak anyway. Fuses will normally tolerate a massive overload for a short period of time as the fuse wire has to get hot enough to burn out before the current is interrupted. A big motor will take a large amount of current (way more than the 13 amp plug rating) for a very short period of time during startup.
It's usually circuit breakers that trip on high inrush currents as they are quicker acting in general.
Freezers and the like will only take a few hundred watts whilst running so the loading from these is not significant, but again they take large surges when first starting. On the whole you'd be unlucky if the freezer chose to start at exactly the same time as the compressor so I don't see sharing the circuit with a few freezers as being a problem.
It's got to be worth re-wiring the fuse and trying again. Try not to clamp the fuse wire too tightly in the holder as this could weaken it around the screws.
I wouldn't upgrade the fuse rating. It will be a 15 amp for a reason, probably to protect the cable between house and garage so unless you can confirm this is rated for more, leave the fuse as is.
You can get slow acting circuit breakers which are designed to withstand high inrush currents and you should be able to get one that plugs into your consumer unit in place of the fuse. I'd expect a fuse in good condition to cope, however.
If you still have problems, try running the compressor through a long extension lead (unwind it from the reel if it gets hot in use). This will give a little resistance and may reduce the inrush current sufficiently.
Kevin