Weird grainy texture in default brush in paint texture mode
I discovered that I had not applied the mirror modifier and that was causing the issue, apparently it was putting the model over itself and the brush did not know which one to paint.

After applying the mirror modifier and making sure I did not have double faces it worked fine.