I reported this same issue on the mailing list:

I root caused it to a problem with Neutron configuration on our Kolla configuration. Alan verified this was fixed long ago in the puppet modules. If your using the packstack installer, you should be good to go.

Maybe this is a regression in the puppet modules or you are installing incorrectly?

Check out the bug and and see if you have the same root cause.

From: ICHIBA Sara <ichi.sara@gmail.com>
Date: Tuesday, June 2, 2015 at 12:19 AM
To: "rdo-list@redhat.com" <rdo-list@redhat.com>
Subject: [Rdo-list] Failed fetching metadata from url http://169.254.169.254/2009-04-04/meta-data

Hey there,

I noticed Lately that when I launch a new VM there are always these error msgs in the log of the VM:

host-10-0-0-5 login: cloud-init[729]: 2015-06-02 07:00:47,204 - util.py[WARNING]: Getting data from <class 'cloudinit.sources.DataSourceOpenStack.DataSourceOpenStack'> failed
cloud-init[729]: 2015-06-02 07:01:03,351 - util.py[WARNING]: Failed fetching metadata from url http://169.254.169.254/2009-04-04/meta-data

checking http://169.254.169.254/2009-04-04/instance-id
successful after 1/20 tries: up 1.04. iid=i-0000003a
failed to get http://169.254.169.254/2009-04-04/meta-data/public-keys/0/openssh-key
warning: no ec2 metadata for public-keys
failed to get http://169.254.169.254/2009-04-04/user-data
warning: no ec2 metadata for user-data
failed to get http://169.254.169.254/2009-04-04/meta-data/placement/availability-zone
warning: no ec2 metadata for availability-zone

Does anyone have an idea what that might be?