Vous pouvez distinguer deux sens et deux construction au verbe « avoir ». Dans votre phrase, il ne s’agit pas du verbe transitif « avoir » signifiant « posséder », et l’adjectif n’est pas épithète. On a ici une construction attributive du verbe « avoir », dans laquelle l’adjectif est donc attribut, et votre règle ne s’applique pas à cette construction.

a) Quand le verbe « avoir » est simplement transitif et signifie par exemple « posséder » ou « porter », et que l’adjectif est épithète, la construction est celle que vous dites : « avoir un » / « ne pas avoir de ».
— il a un chapeau gris –> qu’est-ce qu’il a ? un chapeau gris –> a-t-il ou n’a-t-il pas de chapeau gris ?
Si on retire l’adjectif (il a un chapeau), la phrase garde un sens, c’est ce qui nous indique qu’on a une simple épithète, et que votre règle peut s’appliquer.

b) Quand la construction est attributive, que l’adjectif est donc attribut, la construction « ne pas avoir de » n’aurait pas de sens.
b1) C’est très net avec l’article défini :
— Il a les yeux bleus = ses yeux sont bleus –> il n’a pas les yeux bleus
— Il a les idées claires = ses idées sont claires –> il n’a pas les idées claires
b2) C’est parfois un tout petit peu moins net avec l’article indéfini, car la construction peut suggèrer le sens transitif de « avoir » (qu’est-ce qu’il a ?) :
— Il a une belle tête = sa tête est belle –> il n’a pas une belle tête
— Il a un regard qui inspire confiance = son regard inspire confiance –> il n’a pas un regard qui inspire confiance
— il a un esprit libre = son esprit est libre –> il n’a pas un esprit libre
— il a une nature égoïste = sa nature est égoïste –> il n’a pas une nature égoïste
Puisque la phrase perd sons sens en retirant l’adjectif (il a une tête, il a un regard, il a un esprit, il a une nature), c’est que l’adjectif est attribut, et votre règle ne s’applique pas à cette construction.

c) Parfois, les deux interprétations sont possibles. Par exemple si tous ont un vélo, et qu’on parle de la couleur du vélo de Martin :
* Construction attributive :
— Martin, c’est celui qui a un vélo gris = Martin, c’est celui dont le vélo est gris
— Mais non, Martin n’a pas un vélo gris ! = le vélo de Martin n’est pas gris
* Construction avec verbe transitif et épithète au COD :
— Martin, c’est celui qui a un vélo gris = Martin, c’est celui que vous reconnaîtrez à son vélo gris
— Mais non, Martin n’a pas de vélo gris ! = Martin n’a pas ce type de vélo (voire n’a pas de vélo)
On entend la différence à l’oral, je souligne la syllabe accentuée :
— Il a un vélo gris = construction attributive (comment est son vélo ?)
— Il a un vélo gris = construction transitive avec épithète (que possède-t-il ?)

C’est à cause de l’adjectif et de l’emploi du mot nature…
On ne dit pas  » tu n’as pas de nature égoïste », d’ailleurs,
ni même tu as une nature égoïste…. Je ne sais trop ce que c’est pour une personne, « avoir une nature comme ci ou comme ça ».

j’ai une voiture / je n’ai pas de voiture. Vous avez raison, c’est le cas général mais il y a des exceptions ou d’autres emplois tout simplement.
Je n’ai pas une voiture jaune, mais une voiture rouge.
Tu n’es pas d’un naturel égoïste : voilà ce que j’aurais dit.

Concernant l’emploi du mot « nature », il n’y a ici aucun problème.
Nature – définition Le Robert : Ensemble des caractères, des propriétés qui définissent un être, une chose concrète ou abstraite.
Ensemble des caractères innés de l’espèce, spécialement de l’espèce humaine. La nature de quelqu’un, une nature : ensemble des éléments innés d’un individu. Caractère.

Tu n’as pas de voiture = tu n’as aucune nature
tu n’as pas de voiture jaune = tu n’as aucune voiture jaune

Comme chaque individu ne peut avoir qu’une nature il n’est pas possible de dire : tu n’as aucune nature égoïste  et donc impossible de dire tu n’as pas de nature égoïste