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 ?)