It looks a bit odd for a new build; you can almost imagine that it was only ever intended for decoration. Does the chimney breast extend into the room, or is it built onto the outside as it's got a very deep recess. The stove is only 355mm wide, and is designed to fit into a standard 16" opening, and as you're not going to get a smaller stove, I'm a little perplexed as to what the new installers are going to suggest, so I'd be a little wary of what they suggest.
When I suggested you widen the opening, it's a case of a builder taking a row of bricks out of each side of it, as I think the stoves okay, and just needs a couple of 45 bends to bring it further into the room, but you need a builder to adjust the chimney opening.
As the initial installers aren't Hetas registered, they should at least take the stove back and give a refund, and you might agree to accept a reduced cost for the liner.