The book is Predicate Calculus by Goldrei. Given the hint and other similar exercises, this is the only way I know how to go about this:
Take the set $\text{Th}(\mathcal{N}) \cup \{ \textbf{c} \not = \underbrace{\textbf{1}+...+\textbf{1}}_{n} | n \in \mathbb{N}\}$. Then $\mathbb{N}$ models each finite subset since we can let $\textbf{c}^\mathcal{N}$ be any number that isn't of the form $\underbrace{\textbf{1}+...+\textbf{1}}_{n}$ for the values of $n$ in the subset. Therefore the union has a model, $\mathcal{M}$, lets say with domain $M$. Since the cardinality of this new language is finite, then by the DLS theorem $M$ has cardinality at most $\aleph_0$.
But now I have just changed the language by adding a constant symbol $\textbf{c}$. Is it valid to say that $\mathcal{M}$ models the original langauge because it is a subset of this new langauge?
Now for showing that the two models are not isomorphic. I know the argument show go something like this: Some $n$ in the standard model must get mapped to an element in $M$ that interprets the new constant symbol $\textbf{c}$, but we have $n = \underbrace{1+...+1}_{n}$ yet $\textbf{c}^{\mathcal{M}} \not = \underbrace{1+...+1}_{n}$ for any $n$.
I am having trouble formalizing this. Let $\theta : \mathbb{N} \to M$.
$$(n,\underbrace{1,...,1}_{n}) \in =^{\mathcal{N}}$$ iff
$$(\theta(n),\underbrace{\theta(1),...,\theta(1)}_{n}) \in =^{\mathcal{M}}$$
(actually this an abuse of notation, as the former should be $(n, +^{\mathcal{N}}(\textbf{1}^{\mathcal{N}}, +^{\mathcal{N}} (\textbf{1}^{\mathcal{N}}, +^{\mathcal{N}}(...)) ) )$, but this is far less readable)
Now, by the premise $\theta(n) = \textbf{c}^{\mathcal{M}}$, but what the heck should $\theta(1)$ be? If I am mapping into some general domain then how do I know what the elements are, let alone how $+^{\mathcal{M}}$ and $\cdot^{\mathcal{M}}$ are defined?
If we try to make it more concrete by using what should intuitively be a model, $\mathbb{N} \cup \{ \infty \}$, well first we would have to prove that this is a model of $\text{Th}(\mathcal{N})$ and how do we do that??