When it comes to security-related issues, some are clearly security problems such as remote code execution, some are clearly not (like hardening an already secure function), and some fall into a grey area of “maybe”.
Things that fall under the CWE (Common Weakness Enumeration) and are exploitable (for example, it is not in a dead code path) are clearly vulnerabilities. Note that the CWE is by no means complete, so just because it is not listed there does not mean it isn't a vulnerability. (TODO: example?)
If a flaw can be exploited, it can usually have a CVSS score assigned to it. Typically a vulnerability results in an impact to the Confidentiality, Integrity, or Availability of a component or system.
https://www.first.org/cvss/user-guide
Some vulnerabilities result in leaked information. For example, a vulnerability in a web application might allow user names to be enumerated based on the error received when trying to reset a password, resulting in “user doesn't exist” versus “password reset sent” (see https://cwe.mitre.org/data/definitions/209.html).
Although some side-channel attacks can result in a very limited amount of information being leaked, many of these attacks could be repeated to expose useful information and must therefore be given a CVE.
If a system has a stated security policy like “encryption keys are generated using 160 bits of entropy” but in fact only uses 128 bits, this would be a vulnerability although 128 bits is generally considered to be secure. A system must correctly enforce its stated security policy (see https://cwe.mitre.org/data/definitions/573.html).
Some CVE classes are based on the fact that certain technologies or security mechanisms must be used. For example, single DES is no longer considered secure because 56-bit keys can now be factored on a modern machine in minutes or less. Because of this, any use of DES (or export-grade ciphers in general) would be considered CVE worthy (see https://cwe.mitre.org/data/definitions/327.html).
Other examples include web applications that use HTTP cookies for authentication and do not set the “httponly” flag on them (because it is assumed that an XSS could be present that can be used to steal the cookie).
If a flaw clearly results in a denial of service, such as the “ping of death” (an oversized ICMP packet that causes operating systems to crash when they try to reply to it), this is classified as a CVE vulnerability (see https://cwe.mitre.org/data/definitions/400.html).
However, other flaws are more complicated. For example, if a connection results in memory allocation and no limits are placed on how many connections can be made, this will probably not be classified as a CVE unless another factor is present to make it more exploitable such as holding the connection open for a long period with no timeout (such as the Slowloris attack or SYN Flooding).
Similar to the example in “Does it violate stated security policy?”, if a certificate-creation tool makes no claims about how much entropy it uses, and is updated to use 160 bits instead of 128 bits of entropy, this would be classed as a security hardening issue and not a CVE vulnerability because the original behavior (using 128 bits of entropy) is currently accepted as a secure behavior.