Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks?
Short answer: Not necessarily. Likely nothing fishy is going on.

Longer answer:
The Universal Approximation Theorem (UAT) says nothing about an individual network's capacity to approximate a function. Moreover it says nothing about trainability or generalization.

The UAT roughly says that for any $\epsilon&gt;0$ and any continuous real-valued function $F$ on compact domain $\Omega$ there exists a feed-forward network $f$ with a single hidden layer (with appropriate weights) such that $| F(x)-f(x)|&lt;\epsilon$ for all $x\in\Omega$. Inductively using the shallow UAT, one can prove a deep UAT. So in theory depth offers no more expressiveness. 

Note that this merely guarantees the existence of some appropriately tuned neural network, and not that any particular network can be trained up to that desired accuracy. 

On the other hand, deep neural networks have been seen to be often much better in many applications. This is often attributed to their ability to learn hierarchical representations of the data. The UAT says nothing about generalization, which is the bar by which success is usually measured in practice. Here it is argued that deep networks can approximate compositional functions with less parameters than shallow counterparts. 

But on the other-other hand, it was noticed that sometimes adding more depth can hurt when training a network. But why should it? One could in principle just set the new layer to be the identity. Apparently the later layers were actually trying to approximate the identity but doing it very poorly. So why not learn how different your layer is from the identity? This observation led to Residual Learning which in turn led to some really, really deep networks.