I use a very useful addon to paint.net, called GridMaker (http://forums.getpaint.net/index.php?/topic/4175-grid-maker-plugin/) which lets you make grids as wide/high as you want, so for you can make it 16x16.
My settings for a 256x256:
Horizontal grid step: 16
Horizontal grid step: 16
Checker Board
Top left. (Centered on CROSSING and bottom right work the same)
Everything else unchecked (unless maybe linked with horizontal, which maches same size horizontal and vertical...)
Lastly, something that I guess most of you know, but there might be someone that doesn't, use the pencil instead of the brush, it's much more pixel-accurate.