AWS yum does not work from private subnet (does work from public)

In a very similar situation as the one described in the question I was able to solve it by adding the proxy configuration to /etc/yum.conf.

Like this:

echo "proxy=http://my.proxy.internal:3128/" >> /etc/yum.conf