Floating ips not reachable for new instances

Hello,

Today, I found out a new unexplainable behavior from my OpenStack Essex cluster.
I am running an Essex cluster (Precise packages 2012.1-0ubuntu2.3) with one controller and 4 compute nodes. Everything works just fine, I am able to spin up and down instances create snapshots to my Swift cluster and ping the instances on both private and public interfaces.
The problem I am experiencing at the moment is that when I spin up a new instance, it comes up, I can see the instance's log and it goes all the way to the end (no problem from the instance itself) and can also see the floating ips gets automatically attributed to this new instances but i cannot ping the floating ip (I have the auto_assign_floating_ip = true).
I looked at the nova logs closely and there is not a single warning or error coming in. I tried to restart nova-api, nova-compute and nova-network on the compute nodes but it doesn't seems to change anything.

Do you have a clue on what could possibly happen on these hosts?

Thanks a ton,
Warik