This is what is called a parallel installation. The new stove will not fit in this space without some accommodations for the larger stove. Is the current stove an Englander 13-NC? I don't see how the salesperson would be able to say that "it's fine" without doing the homework of comparing existing measurements with the new stove's requirements. Can you post a shot of the paper with dimensions that you brought into the store?
The Label on the back of the unit says 13-NC-CLP or 123-NC MH. I am not sure exactly which one.