The brushes you are using also may be or a low resolution. E.G. They were created in a small size, and making the size bigger than they were created to do will change the clarity. Just like low res files do when they are added onto a high res file.
I had this problem and found that I had accidentally changed mode from "normal" to "dissolve". When your brush tool is active, check that the mode box on the top menu shows "normal". This solved it for me.