It is probably an issue of pixels interpolation. Even if you paint with the brush at 100% it might be blurry unless you snap it to pixels.

Think this way... If your brush was a perfect 1px thick horizontal line and you touch it to the canvas anywhere other than dead center on a pixel, it will get interpolated as a blurry line.

That's my guess, though I haven't used photoshop for a while... Not sure of the workaround, other than starting larger then scaling the finished product down.

-RobA>