I ran into the same problem again, this time with a BCM 5708 NIC on a Dell 2RU Poweredge 2950. Exactly the same symptoms: the box makes ARPs, which are answered, but the arp cache shows incomplete entries for all IP addresses. Setting the entries manually didn't help - my pings then just seemed to go nowhere. iptables was not getting in the way. There appears to be some discussion about the problem but no solutions...
My setup was a bridged interface that consisted of two bonded NICs to get more bandwith throughput using Cisco port channelling on the switch. Getting rid of the bond and just using a regular bridge on one of the NICs fixed it. Might try the NIC bonding again on the next hardware refresh.