How can addition be non-recursive? Tennenbaum's theorem says neither addition nor multiplication can be recursive in a non-standard model of arithmetic. I assume recursive means computable and computable means computable by a Turing machine (TM).
The 3-state TM described below takes the unary representation of two natural numbers as input and outputs the unary representation of the sum of the two numbers. A unary representation is a string of 1's (possibly empty) followed by a 0. Given the input 110110 this TM will output 111100.
A0:1RB  A1:1RA
B0:0LC  B1:1RB
C0:0Halt  C1:0Halt
This TM halts on any input tape with two 0's. It can add any two standard natural numbers in a finite number of steps. It must also work inside any non-standard model. Assume it didn't. Then we could define the set of numbers, $x$, such that this TM correctly adds $x+x$. Assuming this set has no largest element, it would be an inductive set since it includes all standard natural numbers. A non-standard model can't have an inductive proper subset proving this TM must work in any non-standard model.
Another scenario is when we have a non-standard model in a meta-theory like ZFC. We must assume our meta-theory uses a standard model of arithmetic. The TM above still adds standard natural numbers, but Tennenbaum's theorem says there can't be an algorithm in the meta-theory that computes addition in this non-standard model.
Why can't the TM I describe above compute addition in this non-standard model? Is it simply because the input tape would have to be infinitely long if one of the input numbers is an "infinite" number? 

If you take a countable nonstandard model, you first enumerate that model in $\omega$. That is, you consider the domain of the model to be a set $\{ a_0, a_1, \ldots \}$.
In your algorithm, the input $n$ represents the actual number $n$, and not the element $a_n$ of the model. But this is not what the question is asking, it's asking if there is an algorithm that, given input $\langle n, m \rangle$, outputs a number $k$ such that $a_n + a_m = a_k$. Tenenbaum's theorem says that there is no such algorithm.
