Sorry but you're not right in any way.
Using 'add_users' to determine if the user is an admin is totally wrong. 'add_users' is only a capability, you can give it to users who you trust to perform that task or to create custom roles.
If you're the admin of a WP or WPMS install and wants some user to be able to create user you'll give 'add_users' capability and you expect that he only can do that admin task, and not other ones like manage options, because for managing options exists the 'manage_options' capability.
So using 'add_users' to allow the manage of the options of your plugin you're creating a security flaw allowing users that has no permissions to manage options to manage the security options!
And there's no problem using the "manage_options" capabiliy in any version of WP or WPMS. It's something that exists from the begining of WordPress.
You should seriously consider to fix this. You have a really nice an useful plugin, maybe one of the best for security, but this point is a big flaw.
Anyway, maybe you should consider to create a custom capability to your plugin. This is the way most plugins works today.