Have you tried using the Pencil tool instead of the Brush? The difference between the two is the Pencil applies no antialiasing to your strokes, so if it's a filtering problem, that should reduce or eliminate it.

And following on from RobA's idea, you can change Photoshop's default interpolation method in Edit > Preferences > General. Try Nearest Neighbor to start with. If it is an interpolation issue, then that will make the brush nice and crisp, but it will probably also distort the edges a bit.

Let us know if either or both of those methods improve things or not.