EDIT NOTE: Thanks to Emil Jeřábek's comment, (1) has been modified; $X$ in the theorem has been quantified, and the bold sentence in (4) has been added.
I will first present a counterexample using a structure that has (infinitely many) functions; then I will explain how this functional counterexample can be turned into a relational one.
We begin with some preliminaries:
(1) Recursively saturated models that have elimination of quantifiers are ultra-homogeneous. This is a basic result in model theory.
(2) If $M_0$ and $M_1$ are models of $PA$ (Peano arithmetic), and $M_0$ is a submodel of $M_1$, then $SSy(M_{0})\subseteq SSy(M)$. This follows from the definition of $SSy(M)$ (the standard system of $M$). Recall that for a model $M$ of $PA$, $SSy(M)$ is the collection of subsets of $\omega$ that are "coded" by some element of $M$, where "coded" can be defined in various ways, e.g., as: $X \subseteq \omega$ is coded by $c \in M$ if for all $n \in \omega$, $M \models$ “the $n$-th prime divides $c$” iff $n \in X$.
(3) The heart of this counterexample is the following theorem [it is Theorem 2.3.1 (p.40) of the Kossak-Schmerl text on models of Peano arithmetic].
Theorem. Let $M_0$ be a countable recursively saturated model of $PA$, and suppose $X$ is some fixed subset of $\omega$. Then $M_0$ has elementary end extensions $M_1$ and $M_2$, such that $M_0 \cong M_{1} \cong M_2$, and whenever $M_{3}\models PA$ is an amalgamation of $M_1$ and $M_2$, then $X\in SSy(M_3)$.
(4) Given $M \models PA$, let $M^{+}$ be the EXPANSION of $M$ by the first-order definable functions of $M$. We observe that if $N^{+}$ is a substructure of $M^{+}$, then the reduct $N$ is a model of $PA$ since the universe of $N$ is closed under the functions available in $M^{+}$, and therefore $N$ is an elementary submodel of $M$ because $PA$ has definable Skolem functions. Note, furthermore, that $M^{+}$ eliminates quantifiers, and is also recursively saturated, hence ultrahomogeous.
(1)-(4) show that for a countable recursively saturated model $M$ of $PA$, the collection of substructures of $M^{+}$ do not satisfy amalgamation.
More specifically, thanks to the aforementioned theorem in (3), by first choosing some subset $X$ of $\omega$ that is missing from the standard system of $M$, we can be assured of the existence of (end) embeddings $f_{i}:M^{+}\rightarrow M^{+}$ for $i=0,1$ with the property that if there is a structure $N^{+}$, and embeddings $g_{i}:M\rightarrow N^{+}$ for $i=0,1$, with $g_{0}f_{0}=g_{1}f_{1}$, then by (2) and (4) $N^{+}$ is not a substructure of $M^{+}$.
Now we explain how to obtain a relational counterexample.
Given a model $A$ in a language with functions, let $\cal{A}$ be the relational structure obtained by replacing each $n$-ary function $f$ in $A$ by the usual $(n+1)$-ary relation known as the graph of $f$.
Let $M$ be a countable recursively saturated model of $PA$. To see that the family of substructures of $\cal{M^{+}}$ do not satisfy amalgamation, we simply observe that if $(X,\cdot \cdot \cdot)$ is a substructure of $\cal{M^{+}}$, and $\overline {X}$ is the closure of $X$ under the functions available in $M^{+}$ , then the inclusion map $i_{X}:X\rightarrow \overline{X}$ is an embedding of the substructure of $\cal{M^{+}}$ determined by $X$ into the substructure of $\cal{M^{+}}$ determined by $\overline{X}$. Therefore, if $AP$ holds in this relational context for some amalgamating substructure with universe $X$, by composing each $g_i$ with $i_{X}$ then $AP$ would also have to hold in the functional context.