I don't think this is correct. Forget the metric for the moment and just look at the Hausdorff topology, which says for a metric space two distinct points can be included in two non empty non intersecting open sets.
If $u \in B(u;\epsilon) \subset U$ and $U \subset \overline{A}$ then $u \in B(u;\epsilon) \subset \overline{A}$
So, $ B(u;\epsilon) \cap \overline{A} \ne \emptyset$ and with $ B(u;\epsilon)$ being open this $\implies B(u;\epsilon) \cap A \ne \emptyset \implies \overline{B(u;\epsilon)} \cap A \ne \emptyset$
Proof: $O$ an open set and $O \cap \overline A \ne \emptyset \implies O \cap A \ne \emptyset $
Suppose that $O \cap A = \emptyset $ then no point of $O$ is in $A$ and by the hausdorff property, for any point in A and any point in O there are non-empty non-intersecting open sets containing them. So no point of O can be a limit point of A.
$\overline A = A \cup $ its limit points, and therefore $O \cap \overline A = \emptyset$ which contradicts $O \cap \overline A \ne \emptyset$
Alternately "Intuitively .....therefore there must be a distance at least $ϵ$ between $A$ and $U$. But I have no clue how to show this mathematically." - You can't prove it, it isn't true.
$ B(u;\epsilon) \cap \overline{A} \ne \emptyset$ so there is $x \in B(u;\epsilon) \cap \overline{A}$
For any $\epsilon > 0$ if $x \in \overline A$ then there is some $a \in A$ with $d(x, a) < \epsilon$. So if $x \in B(u;\epsilon)$ then $d(B(u;\epsilon), a) < \epsilon \implies d(U, A) < \epsilon$