No; they are wrong.

I suggest that you print out or otherwise show them a copy of this article in The Guardian, for which an investigative reporter contacted all of the major banks and showed them deeds poll generated by my website, and all of them agreed (eventually: some were slower than others) that they were acceptable. By a “stamp”, they’re probably asking for a “seal”, which hasn’t been required since the 1980s (and in practice wasn’t required for many decades before that).

You’ll note that Nationwide are specifically mentioned in the article as having originally refused these deeds poll, but later changed their stance. Evidently your local branch didn’t get the memo, and you should rub it in their face that a national newspaper is more up-to-date on their internal policy than they are!