I'm rewriting the bug description to match the bug that was actually fixed, which is discussed in comment #1.
The OS::Neutron::FloatingIP resource requires an implicit dependency on any OS::Neutron::RouterInterface resources where the interface connects INTERNAL subnet to which the FloatingIP is connected to the router that provides the external gateway.
Original text follows. The original issue has been moved to bug 1399699.
---
The OS::Neutron::FloatingIP resource has an implicit dependency on any OS::Neutron::RouterGateway resources where the gateway target is the same Network on which the FloatingIP is allocated, since a Router on the Subnet containing the Port must be connected to the Gateway before a FloatingIP can be allocated to it.
However, OS::Neutron::RouterGateway has been deprecated in favour of a property on the OS::Neutron::Router resource. So we also need the same implicit dependency on Routers with the FloatingIP's network specified as the external gateway target.
After discussion on IRC of another bug, it appears that depending on the Router (and by extension the gateway) is insufficient, and we need to depend instead on the RouterInterface that connects the Router to the internal Subnet.
This suggests that it's probably a mistake to have the RouterInterfaces take a Router argument, rather than the other way around; if Router took a list of Ports instead then depending on the Router would be sufficient.