This bug can be reproduced by rally. For example, you can run boot-run-command-delete task. 
the import point here is that you should test you cloud with high pressure, then the bug will be reproduced.
I use rally test my could.
rally configuration is 
{
    "VMTasks.boot_runcommand_delete": [
        {
            "args": {
                "flavor": {
                    "name": "m1.small"
                },
                "image": {
                    "name": "ubuntu-12-04-raw-rally-test"
                },
                "script": "/home/rally/rally/doc/samples/ec_script/ubuntu_ls_test.sh",
                "interpreter": "bash",
                "username": "root",
                "floating_network": "LTQ",
                "use_floatingip": true,
                "availability_zone": "dell420",
            },
            "runner": {
                "type": "constant",
                "times": 1000,
                "concurrency": 40,
                "timeout": 6000
            },
            "context": {
                "users": {
                    "tenants": 1,
                    "users_per_tenant": 1
                },
                "quotas": {
                     "nova": {
                         "instances": -1,
                         "cores": -1,
                         "ram": -1,
                         "fixed_ips": -1,
                         "floating_ips": -1,
                     }
                 },
            }
        }
    ]
}


the rally post error is 
2014-08-15 13:55:53.602 29457 INFO rally.benchmark.runners.base [-] Task bd820c37-2eaf-49d6-99b8-7952d453197d | ITER: 747 END: Error <class 'novaclient.exceptions.BadRequest'>: Error. Unable to associate floating ip (HTTP 400) (Request-ID: req-fa6fa661-e41d-4235-9da7-74ba882dd3c8)

the nova-network.log in the same time is 
2014-08-15 13:55:52.990 23291 DEBUG nova.network.linux_net [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] IPTablesManager.apply completed with success _apply /usr/lib/python2.7/dist-packages/nova/network/linux_net.py:451
2014-08-15 13:55:52.991 23291 DEBUG nova.openstack.common.lockutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Released file lock "iptables" at /var/lock/nova/nova-iptables lock /usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py:208
2014-08-15 13:55:52.991 23291 DEBUG nova.openstack.common.lockutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Got semaphore "ebtables" lock /usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py:166
2014-08-15 13:55:52.992 23291 DEBUG nova.openstack.common.lockutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Attempting to grab file lock "ebtables" lock /usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py:176
2014-08-15 13:55:52.993 23291 DEBUG nova.openstack.common.lockutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Got file lock "ebtables" at /var/lock/nova/nova-ebtables lock /usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py:204
2014-08-15 13:55:52.993 23291 DEBUG nova.openstack.common.lockutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Got semaphore / lock "ensure_ebtables_rules" inner /usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py:245
2014-08-15 13:55:52.994 23291 DEBUG nova.openstack.common.processutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Running cmd (subprocess): sudo nova-rootwrap /etc/nova/rootwrap.conf ebtables -t nat -D PREROUTING --logical-in br100 -p ipv4 --ip-src 10.5.101.41 ! --ip-dst 10.5.101.0/24 -j redirect --redirect-target ACCEPT execute /usr/lib/python2.7/dist-packages/nova/openstack/common/processutils.py:147
2014-08-15 13:55:53.081 23291 DEBUG nova.openstack.common.processutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Result was 255 execute /usr/lib/python2.7/dist-packages/nova/openstack/common/processutils.py:172
2014-08-15 13:55:53.083 23291 DEBUG nova.openstack.common.processutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Running cmd (subprocess): sudo nova-rootwrap /etc/nova/rootwrap.conf ebtables -t nat -I PREROUTING --logical-in br100 -p ipv4 --ip-src 10.5.101.41 ! --ip-dst 10.5.101.0/24 -j redirect --redirect-target ACCEPT execute /usr/lib/python2.7/dist-packages/nova/openstack/common/processutils.py:147
2014-08-15 13:55:53.170 23291 DEBUG nova.openstack.common.processutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Result was 255 execute /usr/lib/python2.7/dist-packages/nova/openstack/common/processutils.py:172
2014-08-15 13:55:53.171 23291 DEBUG nova.openstack.common.lockutils [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Released file lock "ebtables" at /var/lock/nova/nova-ebtables lock /usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py:208
2014-08-15 13:55:53.270 23291 ERROR nova.openstack.common.rpc.amqp [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Exception during message handling
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp Traceback (most recent call last):
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/openstack/common/rpc/amqp.py", line 461, in _process_data
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     **args)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/openstack/common/rpc/dispatcher.py", line 172, in dispatch
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     result = getattr(proxyobj, method)(ctxt, **kwargs)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/floating_ips.py", line 390, in _associate_floating_ip
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     do_associate()
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py", line 246, in inner
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     return f(*args, **kwargs)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/floating_ips.py", line 383, in do_associate
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     interface=interface)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/floating_ips.py", line 367, in do_associate
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     interface, fixed['network'])
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/l3.py", line 115, in add_floating_ip
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     l3_interface_id, network)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/linux_net.py", line 762, in ensure_floating_forward
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     ensure_ebtables_rules(*floating_ebtables_rules(fixed_ip, network))
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py", line 246, in inner
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     return f(*args, **kwargs)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/linux_net.py", line 1590, in ensure_ebtables_rules
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     _execute(*cmd, run_as_root=True)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/network/linux_net.py", line 1190, in _execute
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     return utils.execute(*cmd, **kwargs)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/utils.py", line 177, in execute
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     return processutils.execute(*cmd, **kwargs)
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp   File "/usr/lib/python2.7/dist-packages/nova/openstack/common/processutils.py", line 178, in execute
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp     cmd=' '.join(cmd))
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp ProcessExecutionError: Unexpected error while running command.
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp Command: sudo nova-rootwrap /etc/nova/rootwrap.conf ebtables -t nat -I PREROUTING --logical-in br100 -p ipv4 --ip-src 10.5.101.41 ! --ip-dst 10.5.101.0/24 -j redirect --redirect-target ACCEPT
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp Exit code: 255
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp Stdout: ''
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp Stderr: "The kernel doesn't support a certain ebtables extension, consider recompiling your kernel or insmod the extension.\n"
2014-08-15 13:55:53.270 23291 TRACE nova.openstack.common.rpc.amqp 
2014-08-15 13:55:53.273 23291 ERROR nova.openstack.common.rpc.common [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] Returning exception Unexpected error while running command.
Command: sudo nova-rootwrap /etc/nova/rootwrap.conf ebtables -t nat -I PREROUTING --logical-in br100 -p ipv4 --ip-src 10.5.101.41 ! --ip-dst 10.5.101.0/24 -j redirect --redirect-target ACCEPT
Exit code: 255
Stdout: ''
Stderr: "The kernel doesn't support a certain ebtables extension, consider recompiling your kernel or insmod the extension.\n" to caller
2014-08-15 13:55:53.273 23291 ERROR nova.openstack.common.rpc.common [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] ['Traceback (most recent call last):\n', '  File "/usr/lib/python2.7/dist-packages/nova/openstack/common/rpc/amqp.py", line 461, in _process_data\n    **args)\n', '  File "/usr/lib/python2.7/dist-packages/nova/openstack/common/rpc/dispatcher.py", line 172, in dispatch\n    result = getattr(proxyobj, method)(ctxt, **kwargs)\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/floating_ips.py", line 390, in _associate_floating_ip\n    do_associate()\n', '  File "/usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py", line 246, in inner\n    return f(*args, **kwargs)\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/floating_ips.py", line 383, in do_associate\n    interface=interface)\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/floating_ips.py", line 367, in do_associate\n    interface, fixed[\'network\'])\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/l3.py", line 115, in add_floating_ip\n    l3_interface_id, network)\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/linux_net.py", line 762, in ensure_floating_forward\n    ensure_ebtables_rules(*floating_ebtables_rules(fixed_ip, network))\n', '  File "/usr/lib/python2.7/dist-packages/nova/openstack/common/lockutils.py", line 246, in inner\n    return f(*args, **kwargs)\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/linux_net.py", line 1590, in ensure_ebtables_rules\n    _execute(*cmd, run_as_root=True)\n', '  File "/usr/lib/python2.7/dist-packages/nova/network/linux_net.py", line 1190, in _execute\n    return utils.execute(*cmd, **kwargs)\n', '  File "/usr/lib/python2.7/dist-packages/nova/utils.py", line 177, in execute\n    return processutils.execute(*cmd, **kwargs)\n', '  File "/usr/lib/python2.7/dist-packages/nova/openstack/common/processutils.py", line 178, in execute\n    cmd=\' \'.join(cmd))\n', 'ProcessExecutionError: Unexpected error while running command.\nCommand: sudo nova-rootwrap /etc/nova/rootwrap.conf ebtables -t nat -I PREROUTING --logical-in br100 -p ipv4 --ip-src 10.5.101.41 ! --ip-dst 10.5.101.0/24 -j redirect --redirect-target ACCEPT\nExit code: 255\nStdout: \'\'\nStderr: "The kernel doesn\'t support a certain ebtables extension, consider recompiling your kernel or insmod the extension.\\n"\n']
2014-08-15 13:55:53.274 23291 DEBUG nova.openstack.common.rpc.amqp [req-fa6fa661-e41d-4235-9da7-74ba882dd3c8 737b99c364a64253920c67313655e171 a8c948f6e70648608603b5079537c525] UNIQUE_ID is e652955be8314743ad38bd3f6621a29c. _add_unique_id /usr/lib/python2.7/dist-packages/nova/openstack/common/rpc/amqp.py:341


Hope this help some one to fixed the bug also.