It is possible that iptables is refusing to run because the user executing the process doesn't match the owner of the binary. A process can check both the user's real ID, and the effective user ID (set as a result of the state of the SUID bit on the binary). Some programmes exit if both user IDs don't match.
I cannot say for sure about iptables, but if you can successfully set the bit, then that'd be my guess.
The euid in this case would be root (0) and the uid would be the users real id (500). Some programmes check this and if they are not the equal they stop.
I just found a system with iptables installed and tried it. Without the suid bit on, it does fail with an error, but it was successful when I flipped suid on, so I don't think it is doing what I suggested.
Something that I noticed when I set the permissions is that iptables is actually a sim link that points to iptables-multi. Is this the case in your environment? If so, did you try setting the suid bit on iptables-multi as it doesn't make sense to set it on the simlink (chmod shouldn't allow it anyway).