Description of problem:
If you run 'yum remove <package>' before doing 'yum repolist' on freshly booted instance the following error will occur:
# yum remove perl-devel
Loaded plugins: amazon-id, rhui-lb, security
Setting up Remove Process
Resolving Dependencies
--> Running transaction check
---> Package perl-devel.x86_64 4:5.10.1-136.el6 will be erased
--> Processing Dependency: perl-devel for package: 1:perl-ExtUtils-CBuilder-0.27-136.el6.x86_64
--> Processing Dependency: perl-devel for package: perl-ExtUtils-Embed-1.28-136.el6.x86_64
--> Processing Dependency: perl-devel = 4:5.10.1-136.el6 for package: perl-core-5.10.1-136.el6.x86_64
--> Processing Dependency: perl-devel for package: perl-ExtUtils-MakeMaker-6.55-136.el6.x86_64
--> Processing Dependency: perl-devel for package: 1:perl-ExtUtils-ParseXS-2.2003.0-136.el6.x86_64
--> Processing Dependency: perl-devel for package: perl-Test-Harness-3.17-136.el6.x86_64
--> Processing Dependency: perl-devel for package: perl-Test-Simple-0.92-136.el6.x86_64
--> Running transaction check
---> Package perl-ExtUtils-CBuilder.x86_64 1:0.27-136.el6 will be erased
--> Processing Dependency: perl(ExtUtils::CBuilder) >= 0.15 for package: 1:perl-Module-Build-0.3500-136.el6.x86_64
---> Package perl-ExtUtils-Embed.x86_64 0:1.28-136.el6 will be erased
---> Package perl-ExtUtils-MakeMaker.x86_64 0:6.55-136.el6 will be erased
--> Processing Dependency: perl(ExtUtils::MakeMaker) for package: perl-CPAN-1.9402-136.el6.x86_64
--> Processing Dependency: perl(ExtUtils::MakeMaker) for package: 1:perl-IPC-Cmd-0.56-136.el6.x86_64
--> Processing Dependency: perl-ExtUtils-MakeMaker for package: redhat-lsb-core-4.0-7.el6.x86_64
---> Package perl-ExtUtils-ParseXS.x86_64 1:2.2003.0-136.el6 will be erased
---> Package perl-Test-Harness.x86_64 0:3.17-136.el6 will be erased
---> Package perl-Test-Simple.x86_64 0:0.92-136.el6 will be erased
---> Package perl-core.x86_64 0:5.10.1-136.el6 will be erased
--> Running transaction check
---> Package perl-CPAN.x86_64 0:1.9402-136.el6 will be erased
---> Package perl-IPC-Cmd.x86_64 1:0.56-136.el6 will be erased
--> Processing Dependency: perl(IPC::Cmd) for package: perl-File-Fetch-0.26-136.el6.x86_64
--> Processing Dependency: perl(IPC::Cmd) >= 0.36 for package: perl-File-Fetch-0.26-136.el6.x86_64
--> Processing Dependency: perl(IPC::Cmd) for package: perl-CPANPLUS-0.88-136.el6.x86_64
--> Processing Dependency: perl(IPC::Cmd) for package: 1:perl-Archive-Extract-0.38-136.el6.x86_64
---> Package perl-Module-Build.x86_64 1:0.3500-136.el6 will be erased
---> Package redhat-lsb-core.x86_64 0:4.0-7.el6 will be erased
--> Processing Dependency: redhat-lsb-core for package: libcgroup-0.40.rc1-2.el6.x86_64
--> Processing Dependency: redhat-lsb-core(x86-64) = 4.0 for package: redhat-lsb-printing-4.0-7.el6.x86_64
--> Processing Dependency: redhat-lsb-core(x86-64) = 4.0-7.el6 for package: redhat-lsb-4.0-7.el6.x86_64
--> Processing Dependency: redhat-lsb-core(x86-64) = 4.0 for package: redhat-lsb-graphics-4.0-7.el6.x86_64
--> Running transaction check
---> Package libcgroup.x86_64 0:0.40.rc1-2.el6 will be erased
--> Processing Dependency: libcgroup for package: numad-0.5-9.20130814git.el6.x86_64
--> Processing Dependency: libcgroup for package: policycoreutils-python-2.0.83-19.37.el6.x86_64
---> Package perl-Archive-Extract.x86_64 1:0.38-136.el6 will be erased
---> Package perl-CPANPLUS.x86_64 0:0.88-136.el6 will be erased
---> Package perl-File-Fetch.x86_64 0:0.26-136.el6 will be erased
---> Package redhat-lsb.x86_64 0:4.0-7.el6 will be erased
--> Processing Dependency: redhat-lsb(x86-64) = 4.0-7.el6 for package: redhat-lsb-compat-4.0-7.el6.x86_64
---> Package redhat-lsb-graphics.x86_64 0:4.0-7.el6 will be erased
---> Package redhat-lsb-printing.x86_64 0:4.0-7.el6 will be erased
--> Running transaction check
---> Package numad.x86_64 0:0.5-9.20130814git.el6 will be erased
---> Package policycoreutils-python.x86_64 0:2.0.83-19.37.el6 will be erased
--> Processing Dependency: policycoreutils-python for package: cloud-init-0.7.1-2.el6.noarch
---> Package redhat-lsb-compat.x86_64 0:4.0-7.el6 will be erased
--> Running transaction check
---> Package cloud-init.noarch 0:0.7.1-2.el6 will be erased
--> Finished Dependency Resolution
Could not retrieve mirrorlist https://rhui2-cds01.REGION.aws.ce.redhat.com/pulp/mirror/rhui-client-config/rhel/server/6/x86_64/os error was
14: PYCURL ERROR 6 - "Couldn't resolve host 'rhui2-cds01.REGION.aws.ce.redhat.com'"
Error: Cannot retrieve repository metadata (repomd.xml) for repository: rhui-REGION-client-config-server-6. Please verify its path and try again
 You could try using --skip-broken to work around the problem
 You could try running: rpm -Va --nofiles --nodigest

Version-Release number of selected component (if applicable):
rh-amazon-rhui-client-2.2.92-1.el6_4.noarch

How reproducible:
always

Steps to Reproduce:
1. Start new instance
2. Do 'yum remove package'

Actual results:
Error message

Expected results:
Package is removed

Additional info: