Decidability survives new constants Let $L$ be a finite first order language 
and let $M$ be an $L$-structure with universe $\mathbb{N}$
that interprets all $L$-symbols as recursive sets
(so $M$ is a recursive $L$-structure).
Let $L(c)$ be the extension of $L$ by a new constant symbol $c$, let
$n\in \mathbb{N}$ and let $(M,n)$ be the expansion of $M$ to an 
$L(c)$-structure that interprets $c$ by $n$.
Question:
If $M$ is decidable, is $(M,n)$ decidable, too?
Structures are "decidable" here if the set of sentences of the resp. language that are satisfied in the structure (so, without naming elements of $M$) is recursive.
I assume that this is in general not the case, I even seem to remember that
Church gave a counterexample, but I cannot find it again and my memory 
might play tricks on me. I am actually looking for an answer to this question in the case when $M$ is  nearly model complete, so if somebody can comment on that case, that would be much appreciated.
Remarks: By basic recursion/computation theory:
1) The set of $L(c)$-consequences of the $L$-theory of $M$, is decidable.
2) If $M$ has quantifier elimination (in $L$) then the implication holds.
 A: The answer appears to be negative.
Theorem. There is a computable graph $G$ with a decidable
theory and having a vertex $c$ for which the theory of the pointed
graph $(G,c)$ is not decidable.
Proof. Let us say that a star is a graph with a center node $c$
and a collection of linear rays extending out from this center
node. In other words, it is a connected tree with all vertices
having degree either one or two, except the center, which can have
higher degree. Let us refer to the linear parts of the graph
extending from the center as the rays of the star. Every finite
star can be viewed as coding a finite multi-set of natural
numbers, the multi-set of the lengths of its rays.
 
       /
    | /
   \|/
    c
 
Let $G_0$ be the graph consisting of countably many disjoint
copies of every possible finite star, and let $T$ be the theory of
$G_0$.

I claim, without much argument, that $T$ is a decidable theory. It seems to me that this
theory should eliminate quantifiers down to a collection of
extremely basic assertions about the nature of the stars that the
variables lie on, assertions like "$x$ is distance at most $10$
from the center of its star, distance at most 28 from the end of
its ray, and this star has 4 rays of length $25$ and $12$ but no
ray of size $16$," and "$x$ and $y$ are distance at most 5 on a
ray of the same star" and so on. If this is correct, then $T$ will
be a decidable theory. (Update: 
Emil has given an elegant argument in the comments showing that $T$ is 
decidable, because it is c.e. axiomatizable in a natural way and complete.) 
Now, let $G$ be the graph by adding to $G_0$ an additional
infinite star, with center $c$ and rays of length $n$, for exactly
the $n$ in a fixed c.e. non-computable set $K$. A simple
compactness argument shows that this new graph still satisfies the
theory $T$, since any finite number of such assertions about rays
from $c$ are compatible with $G_0$. Furthermore, I claim that $G$
has a computable presentation. This might seem too much at first,
since $K$ is not computable, but in fact it is enough that $K$ is
merely c.e. To see why, use the odd numbers to make a computable
copy of $G_0$. With the even numbers, we use $0$ as the center of
the infinite star, and whenever $n$ is enumerated into $K$ at time
$t$, then we use the next $n$ available even numbers above $t$ as
the nodes to build the ray coming from $0$. In this way, the edge
relation becomes computable, since the nodes themselves
are big enough numbers to witness whether or not they should be
connected or not. Note that unused nodes are simply extra copies
of the star with no rays. So ultimately, we've got a computable
edge relation on $\mathbb{N}$ making a computable presentation of
the desired graph.
So we've got a computable graph $G$ of a decidable theory $T$, but
the theory of the pointed graph $(G,c)$, where $c=0$ is the center
of the newly added star, is not decidable, since the truth of
 "there is a ray of length $n$ from $c$" is equivalent to
$n\in K$, which is not decidable. QED
(Here is a link to Harizanov's Handbook article on computable model theory, which contains many interesting examples and a highly developed theory.)
