Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?

The question can be stated in a fashion not requiring much background:

Let $M$ be a countable ultra-homogeneous relational structure - namely, a countable set equipped with a bunch of relations on its finite cartesian powers, such that any isomorphism between two finite substructures of $M$ extends to an automorphism of $M$. It is classical (and easy to see) that the age of $M$, namely the class $K$ of finite substructures of $M$ (and isomorphic copies thereof) is a Fraïssé class, and in particular has the Amalgamation Property:

**Amalgamation Property (AP)** - whenever $A,B_i \in K$ for $i=0,1$ and $f_i\colon A \to B_i$ are embeddings, there is $C \in K$ and further embeddings $g_i\colon B_i \to C$ such that $g_0f_0 = g_1f_1$ (i.e., $B_0$ and $B_1$ can be amalgamated in $K$ over $A$).

In all examples I am familiar with, the class of all countable substructures of $M$ also has the same property, but I see no reason why this should be true in general. Any counterexample (or proof that this does hold in general) will be welcome.

[Of course, there are usually going to be in $M$ countable substructures $A_0,A_1$ with an isomorphism $f\colon A_0 \to A_1$ which does not arise from an automorphism - but this does not exclude the possibility of proper embeddings $g_i\colon M \to M$ such that $g_1^{-1} g_0$ extends $f$.]

ADDENDUM: Notice that if $M$ is saturated then its countable substructures have AP, so a counter-example will have to be non saturated, and in particular non $\aleph_0$-categorical, with an infinite language.

ADDENDUM #2: see also A restatement, in terms of the semi-group product of the left-invariant completion of a Polish group, of http://mathoverflow.net/questions/71389