When a permission is set in the plugin.yml, it is loaded after the plugin's onEnable(). The problem is that when the permission is loaded, there is no check to see if the permission is already registered or not, which leads into an error if the permission was added in the plugin's onEnable(). (adding a check would not fix the issue though, keep reading)

To reproduce, declare a permission in the plugin.yml:

permissions:  permission.test.foo:   default: op

Then add it in the onEnable():

String permissionName = "permission.test.foo";
Permission permission = Bukkit.getPluginManager().getPermission(permissionName);
if(permission == null)
{
	permission = new Permission(permissionName);
	Bukkit.getPluginManager().addPermission(permission);
}

And you will get the following exception:
WARN Plugin PluginName v0.1 tried to register permission 'permission.test.foo' but it's already registered
java.lang.IllegalArgumentException: The permission permission.test.foo is already defined!
at org.bukkit.plugin.SimplePluginManager.addPermission(SimplePluginManager.java:598) ~[craftbukkit.jar:git-Bukkit-5e5cf84]
at org.bukkit.craftbukkit.v1_10_R1.CraftServer.loadPlugin(CraftServer.java:353) [craftbukkit.jar:git-Bukkit-5e5cf84]
at org.bukkit.craftbukkit.v1_10_R1.CraftServer.enablePlugins(CraftServer.java:319) [craftbukkit.jar:git-Bukkit-5e5cf84]
at net.minecraft.server.v1_10_R1.MinecraftServer.t(MinecraftServer.java:404) [craftbukkit.jar:git-Bukkit-5e5cf84]
at net.minecraft.server.v1_10_R1.MinecraftServer.l(MinecraftServer.java:369) [craftbukkit.jar:git-Bukkit-5e5cf84]
at net.minecraft.server.v1_10_R1.MinecraftServer.a(MinecraftServer.java:324) [craftbukkit.jar:git-Bukkit-5e5cf84]
at net.minecraft.server.v1_10_R1.DedicatedServer.init(DedicatedServer.java:243) [craftbukkit.jar:git-Bukkit-5e5cf84]
at net.minecraft.server.v1_10_R1.MinecraftServer.run(MinecraftServer.java:514) [craftbukkit.jar:git-Bukkit-5e5cf84]
at java.lang.Thread.run(Thread.java:745) [?:1.8.0_101]

How to fix: (imho)
Load the plugin.yml permissions before onEnable() runs, maybe before onLoad() even.
You can't simply add a check to make sure the permission is not already present because then the permission configuration from plugin.yml would be ignored/overriden by onEnable(), which is not something you would want.
That said, I'd say the issue is about permissions from plugin.yml not being loaded before onEnable().

I did not check with Spigot but I don't see a reason that this behavior would be different.