A new engine will cost about 2 grand and is unnecessary. �700 to change the gaskett is a bit steep, shop around I'm sure you can get it done cheaper. The Gasket's fairly cheap so the cost is mostly labour, sounds like they are having a giraffe. Alternatively get yourself a Haines manual and do it yourself, it's suprisingly simple. A new engine is much more labour and a recon engine will be about �700 on it's own, change the gaskett no contest.
By the way do not be tempted by any "Engines R us" type outfits, they will con you and your car will end up comletely knackered.