Comment 3 for bug 1407417

We have seen two causes of this particular error in the past:
1) If you attempt to associate a floating IP before the Nova instance has completed building
2) If you attempt to associate a floating IP if the instance had issues during build (would be evident in the console log)
3) If you are using Neutron as well and you don't have a properly setup network associated with the instance, which would include:
a) Neutron Router
b) Network Network and Subnet

Just some things to look at and consider.