Let $k,l>1$ be two multiplicatively independent integers. A subset $X$ of $\mathbb{N}^n$ is $k$-recognizable if the set of $k$-ary representations of $X$ is recognized by some finite automaton. Cobham's famous theorem states that a subset of the natural numbers is both $k$-recognizable and $l$-recognizable if and only if it is Presburger-definable (or equivalently: semilinear). We show the following strengthening. Let $X$ be $k$-recognizable, let $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-definable. Then the first-order logical theory of $(\mathbb{N},+,X,Y)$ is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of $(\mathbb{N},+,X)$ is decidable. Our work strengthens and depends on earlier work of Villemaire and Bès. The essence of Cobham's theorem is that recognizability depends strongly on the choice of the base $k$. Our results strengthens this: two non-Presburger definable sets that are recognizable in multiplicatively independent bases, are not only distinct, but together computationally intractable over Presburger arithmetic. This is joint work with Christian Schulz.